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: Accepted

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 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)):  # 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: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    m = int(input())
    a = [[10000 for i in range(n)] for j in range(n)]

    for i in range(m):
        a_i, b_i, d_i = map(int, input().split(","))
        a[a_i][b_i] = d_i//100 - 1
        a[b_i][a_i] = d_i//100 - 1

    w = 0
    v = set()
    v.add(0)

    while len(v) < n:
        min_w   = 10000
        min_idx = 0
        i = 0
        for node in v:
            if min_w > min(a[node]):
                min_w = min(a[node])
                i = node
                min_idx = a[i].index(min_w)
        if min_idx in v:
            a[i][min_idx] = 10000
            continue
        else:
            w += min_w
            v.add(min_idx)

    print(w)

Submission status: Accepted

Solution code:
"""
最小全域木
クラスカル法
"""

#自分の木の根を探し返す、根を直接の親にする
def find(x, par_lst):
  if par_lst[x] == x:
    return x

  root = find(par_lst[x], par_lst)
  par_lst[x] = root
  return root

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

  edges = []
  for _ in range(m):
    a, b, d = map(int, input().split(","))
    edges.append((d // 100 - 1, a, b))

  #コストでソート済みの辺リスト
  edges.sort()
  
  #各ノードの親のリスト
  par_lst = [i for i in range(n)]
  ans = 0
  
  #コストの低い辺からチェック
  for d, a, b in edges:
    par_a = find(a, par_lst)
    par_b = find(b, par_lst)

    #親が違うなら併合
    if par_a != par_b:
      par_lst[par_a] = par_b
      ans += d

  print(ans)

Submission status: Accepted

Solution code:
while 1:
  n=int(input())
  if not n:break
  X={0}
  Y=set(range(n))-X
  s=0
  l=[tuple(map(int,input().split(","))) for _ in range(int(input()))]

  while Y:
    cd=[i for i in l if (i[0] in X and i[1] in Y) or (i[0] in Y and i[1] in X)]
    cd=sorted(cd,key=lambda x:x[2])[0]
    if cd[0] in X and cd[1] in Y:
      X.add(cd[1])
      Y=Y-X
    elif cd[0] in Y and cd[1] in X:
      X.add(cd[0])
      Y=Y-X
    s+=int(cd[2]/100-1)
  print(s)

Submission status: Accepted

Solution code:
# AOJ 0072: Carden Lanternl
# Python3 2018.6.28 bal4u

# UNION-FIND library
class UnionSet:
	def __init__(self, nmax):
		self.size = [1]*nmax
		self.id = [i for i in range(nmax+1)]
	def root(self, i):
		while i != self.id[i]:
			self.id[i] = self.id[self.id[i]]
			i = self.id[i]
		return i
	def connected(self, p, q): return self.root(p) == self.root(q)
	def unite(self, p, q):
		i, j = self.root(p), self.root(q)
		if i == j: return
		if self.size[i] < self.size[j]:
			self.id[i] = j
			self.size[j] += self.size[i]
		else:
			self.id[j] = i
			self.size[i] += self.size[j]
# UNION-FIND library

while True:
	n = int(input())
	if n == 0: break
	u = UnionSet(n)
	m = int(input())
	tbl = []
	for i in range(m):
		a, b, d = map(int, input().split(','))
		tbl.append((d//100-1, a, b))
	tbl.sort()
	ans = 0;
	for x in tbl:
		d, a, b = x
		if not u.connected(a, b):
			u.unite(a, b)
			ans += d
	print(ans)

Submission status: Accepted

Solution code:
while True:
    n=input()
    if n==0:
        break
    graph=[[1<<30]*n for i in xrange(n)]
    for i in xrange(input()):
        a,b,c=map(int,raw_input().strip().split(","))
        graph[a][b]=graph[b][a]=c
    visited=[False]*n
    visited[0],ans=True,0
    while not all(visited):
        t=min( [(i,j,graph[i][j])for j in xrange(n) if not visited[j] for i in xrange(n) if visited[i]],key= lambda x:x[2])
        ans+=t[2]/100-1
        visited[t[1]]=True
    print ans

Submission status: Accepted

Solution code:
INF=1e10

def prim():
    mincost=[INF]*n
    used=[False]*n
    mincost[0]=0
    res=0
    while True:
        v=-1
        for u in range(n):
            if  not used[u] and (v==-1 or mincost[u]<mincost[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        res+=mincost[v]
        for u in range(n):
            mincost[u]=min(mincost[u],cost[v][u])
    return res

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

    cost=[[INF]*n for i in range(n)]
    for i in range(m):
        a,b,d=map(int,raw_input().split(","))
        cost[a-1][b-1]=(d-100)/100
        cost[b-1][a-1]=(d-100)/100
    print prim()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""参考文献
http://ja.wikipedia.org/wiki/クラスカル法
"""
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)
from sys import stdin

while True:
    num_node = int(stdin.readline())
    if not num_node:
        break

    S = []
    for _ in range(int(stdin.readline())):
        S.append([int(s) for s in stdin.readline().split(',')])
    S.sort(key=lambda (n1, n2, d): d, reverse=True)

    forest = {frozenset([i]) for i in range(num_node)}
    spanning = []
    while S:
        node1, node2, distance = S.pop()
        a, b = None, None
        for tree in forest:
            if node1 in tree:
                a = tree
            if node2 in tree:
                b = tree
            if a and b:
                break
        if a != b:
            forest.add(a | b)
            forest.remove(a)
            forest.remove(b)
            spanning.append(distance)
    print(sum((distance // 100) - 1 for distance in spanning))

Submission status: Accepted

Solution code:
while 1:
    n=input()
    if n==0:break
    N=range(n)
    T=N[:]
    M=range(input())
    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)
        b,c=T[x],T[y]
        if b==c:continue
        for i in N:
            if T[i]==b:T[i]=c
        a+=w/100-1
    print a

Submission status: Accepted

Solution code:
while True:
	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:
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__':
    while 1:
        n = input()
        if n == 0:
            break
        m = 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: Accepted

Solution code:
INF = 10 ** 7
while 1:
    n = int(input())
    if n == 0:
        break
    m = int(input())
    M = [[INF] * n for i in range(n)]

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

    d = [INF] * n
    used = [0] * n
    d[0] = 0

    while 1:
        minv = INF
        for i in range(n):
            if (not used[i]) and (d[i] < minv):
                minv = d[i]
                u = i
        if minv == INF:
            break
        used[u] = 1
        for i in range(n):
            if (not used[i]) and M[u][i] != INF and d[i] > M[u][i]:
                d[i] = M[u][i]

    print(int(sum(d)/100)-(n-1))

Submission status: Runtime Error

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,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):
    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")
        ind = float("inf")
        for i in xrange(len(du)):
            pas = passess[i]
            if is_single_in_V(vertexes,pas):
                if min_dist > du[i][2]:
                    min_dist = du[i][2]
                    ind = 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(n):
        data.append( map(int,raw_input().split(",")) )
    solve(n,m,data)

Submission status: Runtime Error

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 = du[i][2]
                    ind = 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(n):
        data.append( map(int,raw_input().split(",")) )
    solve(n,m,data)

Submission status: Runtime Error

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

    while True:
        if all(vs):
            break
        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 vs[p_to]:
                du.pop(i)
                continue
            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)
    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: Runtime Error

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 vs[p_to]:
                du.pop(i)
                break
            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

    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: Runtime Error

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

import sys
import os

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

    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: Runtime Error

Solution code:
import sys
n=input()
N=range(n)
m=input()
A=[sys.maxint]*n
B=[A[:] for i in N]
A=[0]*n
C=[A[:] for i in N]
while 1:
    s=raw_input()
    if s=="0": break
    a,b,w=map(int,s.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: Runtime Error

Solution code:
n,m = int(raw_input()),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
for i in 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