Problem:


灯篭

会津若松市は「歴史の町」として知られています。今から約 400 年前、蒲生氏郷により城下町の骨格が作られましたが、その後、徳川三代将軍家光公の異母弟「保科正之」公を藩祖とする会津藩 23 万石の中心都市として発展しました。今でも市内のいたるところに史跡や昔日の面影が残っているため、毎年、全国から多くの観光客が訪れています。

今年は、ＮＨＫ大河ドラマで「新選組！」が放送されているため、新選組ゆかりの地(*1)として、大幅に観光客が増加しています。そこで市では、市内に点在する史跡を結ぶ通り沿いに 100 m 間隔で灯篭を設置して飾りたてることにしました。灯篭を飾ってある通りを辿れば市内の全ての史跡に到達できるように設置することが条件ですが、一筆書きでたどれる必要はありません。しかし、予算が限られているので設置する灯篭の数を最小限にする必要があります。

史跡と史跡を結ぶ通りのデータを読み込んで、必要最小限の灯篭の数を出力するプログラムを作成して下さい。ただし、史跡と史跡の間の距離は 200 m 以上で、100 の倍数で与えられます。おのおのの史跡から一番近い灯篭までの距離は 100 m で、市内の史跡は 100 箇所以内です。史跡自身には灯篭を設置する必要はありません。

(*1) 新選組は会津藩御預という形で発足、白虎隊の悲劇で知られる会津戊辰戦争に参戦、市内天寧寺に土方歳三が近藤勇の墓を建立

Input

複数のデータセットが与えられます。各データセットは以下の形式で与えられます。

n
m
a1,b1,d1
a2,b2,d2
:
am,bm,dm

各データセットの最初の 1 行には史跡の箇所数 n が与えられます。続いて史跡と史跡を結ぶ通りの数 m が与えられます。続く m 行に カンマで区切られてた3 つの数数 ai, bi, di が与えられます。ai, bi は史跡の番号です。史跡の番号は 0 番から n - 1 番まで振られています。ai bi はそれらを結ぶ通りがあることを示し、di は ai bi 間の道路の距離を表します。

n が 0 のとき入力の最後とします。データセットの数は 20 を超えません。

Output

各データセットに対して、必要最小限の灯篭の数を１行に出力して下さい。

Sample Input

4
4
0,1,1500
0,2,2000
1,2,600
1,3,500
0

Output for the Sample Input

23



Sample input:
4
4
0,1,1500
0,2,2000
1,2,600
1,3,500
0


Sample output:
23

Submission status: Wrong Answer

Solution code:
def warshall_floyd(n, vertices):
    for i in range(n):
        for j in range(n):
            c2 = vertices[j][i]
            for k, (c1, c3) in enumerate(zip(vertices[j], vertices[i])):
                if c1 > c2+c3:
                    vertices[j][k] = c2+c3
    return vertices

while True:
    n = int(input())
    if not n:
        break
    m = int(input())
    inf = float("inf")
    vertices = [[inf if i!=j else 0 for j in range(n)] for i in range(n)]

    for _ in [None]*m:
        s, t, d = map(int, input().split(","))
        vertices[s][t] = d//100-1
        vertices[t][s] = d//100-1

    vertices = warshall_floyd(n, vertices)
    print(min(sum(costs) for costs in vertices))

Submission status: Wrong Answer

Solution code:
N=int(input())
adress={}
counter={}
ans={}
Ans=0
for i in range(int(input())):
    a,b,d=map(int,input().split(","))
    adress[(a,b)]=d
    adress[(b,a)]=d
adress=sorted(adress.items(),key=lambda x:x[0])
for j in adress:
    if j[0][0] in counter:counter[j[0][0]] +=1
    else:counter[j[0][0]]=1
for v in adress:
    if v[0][0] in ans:ans[v[0][0]]=min(v[1],ans[v[0][0]])
    else:ans[v[0][0]]=v[1]
for n,m in counter.items():
    if m==1:del ans[n]
for x,y in ans.items():
    Ans +=y
print(int((Ans/100)-len(ans)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
import os

n = int(input())
m = int(input())

# adjacency matrix
M = [[float('inf') for i in range(n)] for j in range(n)]

for i in range(m):
    a, b, d = map(int, input().split(','))
    M[a][b] = d
    M[b][a] = d

for i in range(m):
    M[i][i] = 0

X = []
Y = [i for i in range(n)]

X.append(0)
Y.remove(0)

light_num = 0
while len(X) != n:
    lst = []
    for x in X:
        for y in Y:
            dist = M[x][y]
            lst.append((dist, x, y))
    lst.sort()

    # selected node
    dist, x, y = lst[0]
    light_num += (dist // 100) - 1

    if x not in X:
        X.append(x)
        Y.remove(x)
    else:
        X.append(y)
        Y.remove(y)
print(light_num)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0072
"""
import sys
from enum import Enum


class Mst(object):
    """ minimum spanning tree """
    INFINITY = 999999999
    class Status(Enum):
        """ ?????????????¨??????¶??? """
        white = 1  # ????¨????
        gray = 2  # ?¨???????
        black = 3  #?¨???????

    def __init__(self, nodes, data):
        self.num_of_pathes = len(data)

        self.color = [Mst.Status.white] * nodes  # ????????????????¨??????¶???
        self.M = self._make_matrix(nodes, data)
        self.d = [Mst.INFINITY] * nodes  #
        self.p = [-1] * nodes  # ????????????????????????????¨??????????

    def _make_matrix(self, nodes, data):
        """ ??£??\???????????????????????\?¶?(-1)????????????????????§(Mst.INFINITY)????????´?????? """
        m = [[Mst.INFINITY] * nodes for _ in range(nodes)]
        for d in data:
            m[d[0]][d[1]] = d[2]
            m[d[1]][d[0]] = d[2]
        return m

    def inf_or_num(self, n):
        if n == -1:
            return Mst.INFINITY
        else:
            return n

    def prim(self):
        """ ??????????????¢?????´?????????????????¨??????????°???¨?????¨????§?????????? """
        self.d[0] = 0  # ??????????????§d[i]???INFINITY??\???????????£???????????????d[0]??????????????§???d[0]??????????´¢???????§????????????¨?????????
        self.p[0] = -1  # d[0]?????????????????§????????????????????????

        while True:
            mincost = Mst.INFINITY
            for i in range(len(self.d)-1):  # V-T????±??????????????????????????????§????????????????°???????????????????
                if self.color[i] != Mst.Status.black and self.d[i] < mincost:
                    mincost = self.d[i]
                    u = i  # ?????????????????????????????????????????\???u??§??¢???????????????

            if mincost == Mst.INFINITY:  # ??¨??????V-T??????????????????????????¨????????§while???????????????
                break

            self.color[u] = Mst.Status.black  # ?????????u???T????±?????????´?????¶?????´??°
            for v in range(len(self.d)):  # v????????????????????????
                if self.color[v] != Mst.Status.black and self.M[u][v] != Mst.INFINITY:  # v???V-T??´ ?????? u??¨v?????????????????????
                    if self.M[u][v] < self.d[v]:  # ????????? u-v?????\?¶?????????????????????????????????´???
                        self.d[v] = self.M[u][v]  # v??????????°???????????????±?????´??°
                        self.p[v] = u  # u???v??????????????¨????????????
                        self.color[v] = Mst.Status.gray

        # ????°???¨?????¨????????????????????????????¨????
        results = []
        for i in range(len(self.p)):
            if self.p[i] != -1:
                results.append(self.M[i][self.p[i]]/100 - 1)
        return int(sum(results))



def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        m = int(input())
        pathes = []
        for _ in range(m):
            pathes.append([int(x) for x in input().split(',')])
        s = Mst(n, pathes)
        result = s.prim()
        print(result)



    # n = 4
    # pathes = [[0, 1, 1500], [0, 2, 2000], [1, 2, 600], [1, 3, 500]]
    # s = Mst(n, pathes)
    # result = s.prim()
    # print(result)




if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
import sys
while 1:
    n=input()
    if n==0:break
    N=range(n)
    m=input()
    M=range(m)
    A=[sys.maxint]*n
    B=[A[:] for i in N]
    A=[0]*n
    C=[A[:] for i in N]
    for i in M:
        a,b,w=map(int,raw_input().split(","))
        B[a][b],B[b][a]=w,w

    s=0
    for i in N:
        x=min(B[i])
        y=B[i].index(x)
        if C[i][y]==0:
            C[i][y],C[y][i]=1,1
            s+=x/100-1
    print s

Submission status: Wrong Answer

Solution code:
import sys
while 1:
    n=input()
    if n==0:break
    m=input()
    M=range(m)
    A=[0]*n
    B=[map(int,raw_input().split(","))for i in M]
    B=sorted(B,key=lambda x:x[2])
    s=0
    c=0
    for i,j,w in B:
        f=[0,2][A[i]]+[0,1][A[j]]
        if f==0:
            A[i],A[j]=1,1
            s+=w/100-1
            c+=2
        elif f==1:
            A[i]=1
            s+=w/100-1
            c+=1
        elif f==2:
            A[j]=1
            s+=w/100-1
            c+=1
        if c==n:break
    print s

Submission status: Wrong Answer

Solution code:
while 1:
    n=input()
    if n==0:break
    N=range(n)
    T=N[:]
    m=input()
    M=range(m)
    S=[map(int,raw_input().split(","))for i in M]
    S=sorted(S,key=lambda x:x[2])        
    a=0
    while S:
        x,y,w=S.pop(0)
        if T[x]==T[y]:continue
        for i in N:
            if T[i]==T[x]:T[i]=T[y]
        a+=w/100-1
    print a

Submission status: Wrong Answer

Solution code:
def prim(n):
    min_cost = [1 << 31] * n
    used = [False] * n
    min_cost[0] = 0
    ret = 0
    while 1:
        v = -1
        for u in range(n):
            if not used[u] and (v == -1 or min_cost[u] < min_cost[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        ret += min_cost[v] - 100

        for u in range(n):
            min_cost[u] = min(min_cost[u], edges[v][u])
    return ret

if __name__ == '__main__':
    n, m = input(), input()
    edges = [[1 << 30] * n for _ in xrange(n)]
    for i in xrange(m):
        a, b, cost = map(int, raw_input().split(','))
        edges[a][b] = cost
        edges[b][a] = cost
    print (prim(n) + 100) / 100

Submission status: Time Limit Exceeded

Solution code:
# http://ja.wikipedia.org/wiki/%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95

class vertex:
    def __init__(self):
        self.min_distance = float("inf")
        self.distance = float("inf")
        self.parent = None
        self.minimum_adjacency_list = []
        self.is_in_Q = True
        self.is_in_V = False

def is_single_in_V(v,p):
    a = v[p[0]].is_in_V
    b = v[p[1]].is_in_V
    return ( a and not b ) or ( not a and b )
def all_in_V(v):
    for e in v:
        if not e.is_in_V:
            return False
    return True
def add_in_V(v,pa):
    v[pa[0]].is_in_V = True
    v[pa[1]].is_in_V = True

def solve(nu,mu,du):
    V= []
    E = []
    vertexes = [vertex() for i in xrange(nu)]
    vertexes[0].distance = 0
    V.append(vertexes[0])
    vertexes[0].is_in_V = True
    distances = [ e[2] for e in du ]
    passess = [ e[0:2] for e in du]

    while True:
        if all_in_V(vertexes):
            break
        min_dist = float("inf")
        for i in xrange(len(du)):
            pas = passess[i]
            if is_single_in_V(vertexes,pas):
                min_dist = min( min_dist, distances[i] )
        ind = distances.index(min_dist)
        E.append(min_dist)
        add_in_V(vertexes,passess[ind])
    print sum(E)/100 - len(E)




while True:
    n = input()
    if n == 0:
        exit()
    m = input()
    data = []
    for i in xrange(n):
        data.append( map(int,raw_input().split(",")) )
    solve(n,m,data)

Submission status: Time Limit Exceeded

Solution code:
def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

def fmin(a, b):
    if a < 0:
        return b
    if b < 0:
        return a
    return min(a,b)

while True:
    n = int(input())
    if n == 0:
        break
    m = int(input())

    table = [[-1 for i in range(m)] for j in range(m)]
    X = [i for i in range(m)]
    for i in range(m):
        a,b,c = [int(i) for i in input().split(",")]
        table[a][b] = c // 100 - 1
        table[b][a] = c // 100 - 1

    X.remove(0)
    costs = [-1 for i in range(m)]
    for i in range(m):
        costs[i] = table[0][i]
    cost = 0

    while True:
        post = -1
        mm = -1
        #print("X:",X)
        #print("costs:",costs)
        for i in range(len(X)):
            if mm == -1:
                mm = costs[X[i]]
                post = X[i]
            elif costs[X[i]] < mm and costs[X[i]] != -1:
                mm = costs[X[i]]
                post = X[i]
            #print("i:",i,"mcost:",mm)
        cost += mm

        for i in range(len(X)):
            costs[X[i]] = fmin(costs[X[i]], table[post][X[i]])

        #print("mcost:", mm, "post:", post)
        X.remove(post)
        if len(X) == 0:
            break

    print(cost)

Submission status: Time Limit Exceeded

Solution code:
def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

def fmin(a, b):
    if a < 0:
        return b
    if b < 0:
        return a
    return min(a,b)

while True:
    n = int(input())
    if n == 0:
        break
    m = int(input())

    table = [[-1 for i in range(m)] for j in range(m)]
    X = [i for i in range(m)]
    for i in range(m):
        a,b,c = [int(i) for i in input().split(",")]
        table[a][b] = c // 100 - 1
        table[b][a] = c // 100 - 1

    X.remove(0)
    costs = [-1 for i in range(m)]
    for i in range(m):
        costs[i] = table[0][i]
    cost = 0

    for l in range(m+m):
        post = -1
        mm = -1
        #print("X:",X)
        #print("costs:",costs)
        for i in range(len(X)):
            if mm == -1:
                mm = costs[X[i]]
                post = X[i]
            elif costs[X[i]] < mm and costs[X[i]] != -1:
                mm = costs[X[i]]
                post = X[i]
            #print("i:",i,"mcost:",mm)
        cost += mm

        for i in range(len(X)):
            costs[X[i]] = fmin(costs[X[i]], table[post][X[i]])

        #print("mcost:", mm, "post:", post)
        X.remove(post)
        if len(X) == 0:
            break

    print(cost)

Submission status: Accepted

Solution code:
def kruskal(n: int, edges: list) -> int:
    tree = [-1]*n

    def get_root(x):
        if tree[x] < 0:
            return x
        else:
            tree[x] = get_root(tree[x])
            return tree[x]

    def unite(x, y):
        x, y = get_root(x), get_root(y)
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    edges.sort()
    total = 0
    cnt = 0
    for w, s, t in edges:
        if unite(s, t):
            cnt += 1
            total += w
            if cnt == n - 1:
                break

    return total

while True:
    n = int(input())
    if not n:
        break
    m = int(input())
    inf = float("inf")

    edges = []
    for _ in [None]*m:
        s, t, d = map(int, input().split(","))
        edges.append((d//100-1, s, t))

    print(kruskal(n, edges))

Submission status: Accepted

Solution code:
def kruskal(n: int, edges: list) -> int:
    tree = [-1]*n

    def get_root(x):
        if tree[x] < 0:
            return x
        tree[x] = get_root(tree[x])
        return tree[x]

    def unite(x, y):
        x, y = get_root(x), get_root(y)
        if x != y:
            big, small = (x, y) if tree[x] < tree[y] else (y, x)
            tree[big] += tree[small]
            tree[small] = big
        return x != y

    return sum(w for (w, _, _), _ in zip(filter(lambda p: unite(p[1], p[2]), sorted(edges)), range(n)))

while True:
    n = int(input())
    if not n:
        break
    m = int(input())
    inf = float("inf")

    edges = []
    for _ in [None]*m:
        s, t, d = map(int, input().split(","))
        edges.append((d//100-1, s, t))

    print(kruskal(n, edges))

Submission status: Accepted

Solution code:
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1


while 1:
    N = int(input())
    if N == 0:
        break
    *p, = range(N)
    M = int(input())
    E = []
    for i in range(M):
        a, b, d = map(int, input().split(','))
        E.append((d, a, b))
    E.sort()
    ans = 0
    for c, a, b in E:
        if unite(a, b):
            ans += (c - 100) // 100
    print(ans)

Submission status: Accepted

Solution code:
# http://ja.wikipedia.org/wiki/%E3%83%97%E3%83%AA%E3%83%A0%E6%B3%95

class vertex:
    def __init__(self):
        self.is_in_V = False

def is_single_in_V(v,p):
    a = v[p[0]].is_in_V
    b = v[p[1]].is_in_V
    return ( a and not b ) or ( not a and b )

def all_in_V(v):
    for e in v:
        if not e.is_in_V:
            return False
    return True

def add_in_V(v,d):
    v[d[0]].is_in_V = True
    v[d[1]].is_in_V = True

def remove_all_in_V_pass(v,d):
    for i in xrange(len(d)):
        try:
            if v[d[i][0]].is_in_V and v[d[i][1]].is_in_V:
                d.pop(i)
        except:
            pass

def solve(nu,mu,du):
    E = []
    vertexes = [vertex() for i in xrange(nu)]
    vertexes[0].is_in_V = True

    while True:
        if all_in_V(vertexes):
            break
        min_dist,ind = float("inf"),float("inf")
        for i in xrange(len(du)):
            if is_single_in_V(vertexes,du[i][0:2]):
                if min_dist > du[i][2]:
                    min_dist,ind = du[i][2],i
        E.append(min_dist)
        add_in_V(vertexes,du[ind])
        du.pop(ind)
        remove_all_in_V_pass(vertexes,du)
    print sum(E)/100 - len(E)

while True:
    n = input()
    if n == 0:
        exit()
    m = input()
    data = []
    for i in xrange(m):
        data.append( map(int,raw_input().split(",")) )
    solve(n,m,data)

Submission status: Accepted

Solution code:
def solve(nu,mu,du):
    E = []
    vs = [False]*nu
    vs[0] = True

    while True:
        min_dist,ind = float("inf"),float("inf")
        for i in xrange(len(du)):
            p_from = du[i][0]
            p_to = du[i][1]
            if ( vs[p_from] and not vs[p_to] ) or ( not vs[p_from] and vs[p_to]):
                if min_dist > du[i][2]:
                    min_dist,ind,pf,pt = du[i][2],i,p_from,p_to
        E.append(min_dist)
        vs[pf] = vs[pt] = True
        du.pop(ind)
        if all(vs):
            break
        for i in xrange(len(du)):
            try:
                if vs[du[i][0]] and vs[du[i][1]]:
                    du.pop(i)
            except:
                pass

    print sum(E)/100 - len(E)

while True:
    n = input()
    if n == 0:
        exit()
    m = input()
    data = []
    for i in xrange(m):
        data.append( map(int,raw_input().split(",")) )
    solve(n,m,data)

Submission status: Accepted

Solution code:
def solve(nu,mu,du):
    E = []
    vs = [False]*nu
    vs[0] = True

    while True:
        min_dist,ind = float("inf"),float("inf")
        for i in xrange(len(du)):
            p_from = du[i][0]
            p_to = du[i][1]
            dist = du[i][2]
            if ( vs[p_from] and not vs[p_to] ) or ( not vs[p_from] and vs[p_to]):
                if min_dist > dist:
                    min_dist,ind,pf,pt = dist,i,p_from,p_to
        E.append(min_dist)
        vs[pf] = vs[pt] = True
        du.pop(ind)
        if all(vs):
            break
        for i in xrange(len(du)):
            try:
                if vs[du[i][0]] and vs[du[i][1]]:
                    du.pop(i)
            except:
                pass

    print sum(E)/100 - len(E)

while True:
    n = input()
    if n == 0:
        exit()
    m = input()
    data = []
    for i in xrange(m):
        data.append( map(int,raw_input().split(",")) )
    solve(n,m,data)

Submission status: Accepted

Solution code:
def solve(nu,mu,du):
    E = []
    vs = [False]*nu
    vs[0] = True

    while True:
        min_dist,ind = float("inf"),float("inf")
        for i in xrange(len(du)):
            if ( ( vs[du[i][0]] and not vs[du[i][1]] ) or ( not vs[du[i][0]] and vs[du[i][1]]) ) and min_dist > du[i][2]:
                min_dist,ind,pf,pt = du[i][2],i,du[i][0],du[i][1]
        E.append(min_dist)
        vs[pf] = vs[pt] = True
        du.pop(ind)
        if all(vs):
            break
        for i in xrange(len(du)):
            try:
                if vs[du[i][0]] and vs[du[i][1]]:
                    du.pop(i)
            except:
                pass

    print sum(E)/100 - len(E)

while True:
    n = input()
    if n == 0:
        exit()
    m = input()
    data = []
    for i in xrange(m):
        data.append( map(int,raw_input().split(",")) )
    solve(n,m,data)

Submission status: Accepted

Solution code:
def solve(nu,mu,du):
    E = []
    vs = [False]*nu
    vs[0] = True

    while True:
        min_dist,ind = float("inf"),float("inf")
        for i in xrange(len(du)):
            if ( ( vs[du[i][0]] and not vs[du[i][1]] ) or ( not vs[du[i][0]] and vs[du[i][1]]) ) and min_dist > du[i][2]:
                min_dist,ind,pf,pt = du[i][2],i,du[i][0],du[i][1]
        E.append(min_dist)
        vs[pf] = vs[pt] = True
        du.pop(ind)
        if all(vs):
            break
        for e in du:
            if vs[e[0]] and vs[e[1]]:
                du.remove(e)
    print sum(E)/100 - len(E)

while True:
    n = input()
    if n == 0:
        exit()
    m = input()
    data = []
    for i in xrange(m):
        data.append( map(int,raw_input().split(",")) )
    solve(n,m,data)

Submission status: Accepted

Solution code:
def solve(nu,mu,du):
    E = []
    vs = [False]*nu
    vs[0] = True

    while True:
        min_dist,ind = float("inf"),float("inf")
        for i in xrange(len(du)):
            if ( ( vs[du[i][0]] and not vs[du[i][1]] ) or ( not vs[du[i][0]] and vs[du[i][1]]) ) and min_dist > du[i][2]:
                min_dist,ind,pf,pt = du[i][2],i,du[i][0],du[i][1]
        E.append(min_dist)
        vs[pf] = vs[pt] = True
        du.pop(ind)
        if all(vs):
            break

        for i in xrange(len(du)):
            try:
                if vs[du[i][0]] and vs[du[i][1]]:
                    du.pop(i)
            except:
                pass

    print sum(E)/100 - len(E)

while True:
    n = input()
    if n == 0:
        exit()
    m = input()
    data = []
    for i in xrange(m):
        data.append( map(int,raw_input().split(",")) )
    solve(n,m,data)

Submission status: Accepted

Solution code:
while(1):
    n=int(raw_input())
    if n==0:
        break
    m=int(raw_input())
    distlist=[[] for x in range(n)]
    for i in range(m):
        [a,b,d]=[int(x) for x in raw_input().split(',')]
        distlist[a].append((b,d))
        distlist[b].append((a,d))
        
    visited=[0]
    notyet={}
    for i in range(1,n):
        notyet[i]=float('inf')
    toro=0
    for pk in distlist[0]:
        dest=pk[0]
        dd=pk[1]
        notyet[dest]=dd
        
    while len(notyet)!=0:
        #search for smallest dist
        smallest=float('inf')
        K=0
        for k in notyet:
            if notyet[k]<smallest:
                smallest=notyet[k]
                K=k
        #print smallest,K,notyet
        toro=toro+smallest/100-1
        for pk in distlist[K]:
            dest=pk[0]
            dd=pk[1]
            if dest in notyet:
                notyet[dest]=min(notyet[dest],dd)
        del notyet[K]
    print toro

Submission status: Accepted

Solution code:
while 1:
    n=int(raw_input())
    if n==0:
        break
    m=int(raw_input())
    s=[map(int ,raw_input().split(',')) for i in range(m)]
    s=sorted(s, key=lambda x:x[2])
    ls=range(n)
    ref=ls[:]
    ans=0
    while s:
        x,y,d=s.pop(0)
        a,b=ref[x],ref[y]
        if a!=b:
            for j in ls:
                if ref[j]==a:
                    ref[j]=b
            ans+=d/100-1
    print ans

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import collections
import heapq


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
DIV = 100
INF = 2 ** 31 - 1


def compute_mst_prim(max_v, adj_list):
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                w = v_cost
                if w < key[v]:
                    key[v] = w
                    heapq.heappush(pq, (w, v))
                    in_pq[v] = True
    return key


def compute_number_of_lanterns(max_v, adj_list):
    key = compute_mst_prim(max_v, adj_list)
    return sum(x - 1 for x in key.values() if x > 0)


def main():
    while True:
        n = int(input())
        if n == 0:
            break
        m = int(input())
        adj_list = collections.defaultdict(set)
        for _ in range(m):
            a, b, w = map(int, input().split(","))
            adj_list[a].add((b, w // DIV))
            adj_list[b].add((a, w // DIV))
        print(compute_number_of_lanterns(n, adj_list))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

while True:
    n = int(raw_input())
    if n == 0:
        break
    m = int(raw_input())
    M = [[sys.maxint for j in range(n)] for i in range(n)]
    for i in range(n):
        M[i][i] = 0
    for i in range(m):
        a, b, d = map(int, raw_input().split(','))
        M[a][b] = d/100 - 1
        M[b][a] = M[a][b]
    X = set([0])
    Y = set(range(n)[0:])
    cost = 0
    while len(Y) > 0:
        mcost = sys.maxint
        for ex in X:
            for ey in Y:
                if mcost > M[ex][ey]:
                    mcost = M[ex][ey]
                    et = ey
        X.add(et)
        Y.remove(et)
        cost += mcost
    print cost

Submission status: Accepted

Solution code:
class UnionFind:
  def __init__(self, size):
    self.table = [-1 for _ in xrange(size)]

  def find(self, x):
    while self.table[x] >= 0: x = self.table[x]
    return x

  def union(self, x, y):
    s1 = self.find(x)
    s2 = self.find(y)
    if s1 != s2:
      if self.table[s1] >= self.table[s2]:
        self.table[s1] += self.table[s2]
        self.table[s2] = s1
      else:
        self.table[s2] += self.table[s1]
        self.table[s1] = s2
      return True
    return False

def hash(n, s, g):
  return n*s+g

def dehash(n, hs):
  return [(hs-hs%n)/n, hs%n]

def kruskal(n, path):
  path = sorted(path.items(), key=lambda x:x[1])
  selected = {}
  union = UnionFind(n)
  for i in xrange(len(path)):
    k,v = path[i]
    s,g = dehash(n, k)
    if union.union(s, g):
      selected[k] = v
  return selected

# main
while True:
  n = int(raw_input())
  if n==0:
    break
  m = int(raw_input())
  path = {}
  for _ in xrange(m):
    a,b,d = map(int, raw_input().split(","))
    path[hash(n, a, b)] = d/100-1
  result = kruskal(n, path)
  sumdist = 0
  for v in result.values():
    sumdist += v
  print sumdist

Submission status: Accepted

Solution code:
class Wood:
  def __init__(self,num,noods,edges):
    self.num = num
    self.noods = noods
    self.edges = edges
  def cons(self,other):
    self.noods.extend(other.noods)
    self.edges.extend(other.edges)

class Edge:
  def __init__(self,n1,n2,length):
    self.n1 = n1
    self.n2 = n2
    self.length = length

def check(woods,edge):
  if woods[edge.n1].num != woods[edge.n2].num:
    woods[edge.n1].cons(woods[edge.n2])
    woods[edge.n1].edges.append(edge)
    for i in woods[edge.n1].noods:
      woods[i] = woods[edge.n1]
while True:
  n = int(input())
  if n == 0:
    break
  m = int(input())
  e = []
  woods = []
  for i in range(m):
    n1,n2,length = map(int,input().split(","))
    edge = Edge(n1,n2,length)
    e.append(edge)
  e = sorted(e,key=lambda x:x.length)
  for i in range(n):
    wood = Wood(i,[i],[])
    woods.append(wood)
  for edge in e:
    check(woods,edge)
  s = 0
  for edge in woods[0].edges:
    s += edge.length//100-1
  print(s)

Submission status: Accepted

Solution code:
class Wood:
  def __init__(self,noods,edges):
    self.noods = noods
    self.edges = edges
  def cons(self,other):
    self.noods.extend(other.noods)
    self.edges.extend(other.edges)

class Edge:
  def __init__(self,n1,n2,length):
    self.n1 = n1
    self.n2 = n2
    self.length = length

def check(woods,edge):
  w1 = woods[edge.n1]
  w2 = woods[edge.n2]
  if w1.noods!= w2.noods:
    w1.cons(w2)
    w1.edges.append(edge)
    for i in w1.noods:
      woods[i] = w1
while True:
  n = int(input())
  if n == 0:
    break
  m = int(input())
  e = []
  woods = []
  for i in range(m):
    n1,n2,length = map(int,input().split(","))
    edge = Edge(n1,n2,length)
    e.append(edge)
  e = sorted(e,key=lambda x:x.length)

  for i in range(n):
    wood = Wood([i],[])
    woods.append(wood)

  for edge in e:
    check(woods,edge)

  s = 0
  for edge in woods[0].edges:
    s += edge.length//100-1
  print(s)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os

for s in sys.stdin:
    n = int(s) # node num
    if n == 0:
        break

    m = int(input()) # edge num

    # adjacency matrix
    M = [[float('inf') for i in range(n)] for j in range(n)]

    for i in range(m):
        a, b, d = map(int, input().split(','))
        M[a][b] = d
        M[b][a] = d

    for i in range(n):
        M[i][i] = 0

    X = [] # selected
    Y = [i for i in range(n)] # not selected

    X.append(0)
    Y.remove(0)

    light_num = 0
    while len(X) != n:
        lst = []
        for x in X:
            for y in Y:
                dist = M[x][y]
                lst.append((dist, x, y))
        lst.sort()

        # selected node
        dist, x, y = lst[0]
        light_num += (dist // 100) - 1

        if x not in X:
            X.append(x)
            Y.remove(x)
        else:
            X.append(y)
            Y.remove(y)
    print(light_num)