Problem:


便利な町

 来春卒業するAさんは、就職を機に引越しをすることにしました。就職する会社は、オフィスがいくつかの町にあって、日によって出勤するオフィスが違います。そこでAさんは,どこのオフィスに
行くにも時間の短い町に住もうと考えました。

 そこであなたは、Aさんを助けるため、住むのに一番便利な町を探すことになりました。

 町には 0 から始まる番号が振られており、町と町の間には道があります。それぞれの道に対して通勤時間が決まっています。Aさんがある町に住んでいる場合に、自分の町のオフィスまでの通勤時間は 0 とします。このときに全ての町までの通勤時間の総和を考えます。例えば、町と道の配置が上の図のようになっていて、Aさんが町1に住んだ場合には、それぞれの町までの通勤時間は

   町 0 まで 80

   町 1 まで  0

   町 2 まで 20

   町 3 まで 70

   町 4 まで 90

となり、総和は 260 となります。

道の数と、全ての道の情報を入力とし、それぞれの町に住んだ場合の通勤時間の総和を計算し、それが最小となる町の番号と、そのときの通勤時間の総和を出力するプログラムを作成してください。ただし、通勤時間の総和が最小となる町が複数ある場合は、一番小さい町の番号及びその時の通勤時間の総和を出力してください。町の総数は 10 以下、道の総数は 45 以下とし、全ての道は双方向に移動でき、通勤時間は方向によって変わらないものとします。また、どの町からでもその他全ての町への 経路があるものとします。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。 各データセットは以下の形式で与えられます。

n
a1 b1 c1
a2 b2 c2
:
an bn cn

１行目に道の数 n (1 ≤ n ≤ 45) が与えられます。続く n 行に i 番目の道の情報が与えられます。
ai, bi (0 ≤ ai, bi ≤ 9) は i 番目の道がつないでいる町の番号、ci (0 ≤ ci ≤ 100) はその道の通勤時間を表します。

Output

データセット毎に、通勤時間の総和が最小になる町の番号及びその時の通勤時間の総和を空白区切りで１行に出力します。

Sample Input

6     
0 1 80
1 2 20
0 2 60
2 3 50
3 4 60
1 4 90
2
0 1 1
1 2 1
0

Output for the Sample Input

2 240
1 2



Sample input:
6
0 1 80
1 2 20
0 2 60
2 3 50
3 4 60
1 4 90
2
0 1 1
1 2 1
0


Sample output:
2 240
1 2

Submission status: Wrong Answer

Solution code:


while True:
    n = int(input())
    if n == 0:
        break
    AM = [[10000 ]*10 for i in range(10)]
    for i in range(10):
        AM[i][i] = 0
    maxNum = -1
    for i in range(n):
        a, b,c = map(int,input().split())
        AM[a][b] = c
        AM[b][a] = c
        maxNum = max(maxNum,a,b)
    # print(AM[:maxNum][:maxNum])
    # print(maxNum)
    sumDistance = [0]*(maxNum+1)
    for i in range(maxNum+1):
        for j in range(maxNum+1):
            for k in range(maxNum+1):
                AM[i][j] = min(AM[i][j],AM[i][k]+AM[k][j])
            sumDistance[i] += AM[i][j]
    # print(AM)
    # print(sumDistance)
    tmp = min(enumerate(sumDistance), key=lambda x: x[1])
    print(tmp[0],tmp[1])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0189
AC
"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp_ik = dp[i][k]
                dp_kj = dp[k][j]
                if dp[i][j] < dp_ik + dp_kj:
                    dp[i][j] = dp_ik + dp_kj


def main(args):
    while True:
        n_max = 9+1
        n = int(input())
        if n == 0:
            break
        dp = [[float('inf')] * n_max for _ in range(n_max)]
        for i in range(n_max):
            dp[i][i] = 0

        max_town = 0
        for _ in range(n):
            a, b, c = map(int, input().split())
            dp[a][b] = c
            dp[b][a] = c
            max_town = max(max_town, a, b)

        warshallFloyd(max_town + 1, dp)


        min_dist = float('inf')
        town_live = -1
        for i, d in enumerate(dp[:max_town+1]):
            sum_dist = 0
            for ele in d[:max_town+1]:
                sum_dist += ele
            if sum_dist < min_dist:
                min_dist = sum_dist
                town_live = i

        print('{} {}'.format(town_live, min_dist))



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

Submission status: Wrong Answer

Solution code:
road = int(input())
while road > 0:
    answer = [[float("inf") if n != m else 0 for n in range(10)] for m in range(10)]
    city = 0
    for _ in range(road):
        c1, c2, w = (int(n) for n in input().split(" "))
        answer[c1][c2] = w
        answer[c2][c1] = w
        city = max(city, c1, c2)
    for i in range(city):
        for j in range(city):
            for k in range(city):
                answer[j][k] = min(answer[j][k], answer[j][i] + answer[i][k])
    sum_ans = [-1 , float("inf")]
    for i in range(city):
        if sum(answer[i][:city]) < sum_ans[1]:
            sum_ans = [i, sum(answer[i][:city])]
    print(*sum_ans)
    road = int(input())

Submission status: Wrong Answer

Solution code:
NULL = 10000
TOWN_COUNT = 10

while True:

    input_count = int(input())

    if input_count == 0:
        break

    adjacency_matrix = [[NULL] * TOWN_COUNT for _ in range(TOWN_COUNT)]

    for lp in range(TOWN_COUNT):
        adjacency_matrix[lp][lp] = 0

    need_index = 0

    for _ in range(input_count):
        start, end, time = [int(item) for item in input().split(" ")]

        adjacency_matrix[start][end] = time
        adjacency_matrix[end][start] = time

        need_range = max(need_index, start, end)

    for a in range(need_range + 1):
        for b in range(need_range + 1):
            for c in range(need_range + 1):
                adjacency_matrix[a][c] = min(adjacency_matrix[a][b] + adjacency_matrix[b][c], adjacency_matrix[a][c])

    min_time = NULL
    min_index = -1

    for index, item in enumerate(adjacency_matrix):
        need_element = [item2 for item2 in item if 0 < item2 < NULL]

        if 0 < len(need_element):
            time = sum(need_element)

            if time < min_time:
                min_time = time
                min_index = index

    print(min_index, min_time)

Submission status: Wrong Answer

Solution code:
NULL = 10000
TOWN_COUNT = 10

while True:

    input_count = int(input())

    if input_count == 0:
        break

    adjacency_matrix = [[NULL] * TOWN_COUNT for _ in range(TOWN_COUNT)]

    for lp in range(TOWN_COUNT):
        adjacency_matrix[lp][lp] = 0

    need_range = 0

    for _ in range(input_count):
        start, end, time = [int(item) for item in input().split(" ")]

        adjacency_matrix[start][end] = time
        adjacency_matrix[end][start] = time

        need_range = max(need_range, start, end)

    for a in range(need_range + 1):
        for b in range(need_range + 1):
            for c in range(need_range + 1):
                adjacency_matrix[a][c] = min(adjacency_matrix[a][b] + adjacency_matrix[b][c], adjacency_matrix[a][c])

    min_time = NULL
    min_index = -1

    for index, item in enumerate(adjacency_matrix):
        need_element = [item2 for item2 in item if 0 < item2 < NULL]

        if 0 < len(need_element):
            time = sum(need_element)

            if time < min_time:
                min_time = time
                min_index = index

    print(min_index, min_time)

Submission status: Wrong Answer

Solution code:
INF = 10 ** 10
while True:
  n = int(input())
  if n == 0:
    break

  costs = [[INF] * 10 for _ in range(10)]
  for i in range(10):
    costs[i][i] = 0
  
  city = set()
  for _ in range(n):
    a, b, c = map(int, input().split())
    city = city | {a, b}
    costs[a][b] = c
    costs[b][a] = c 
  
  city = sorted(list(city))
  
  for i in range(10):
    for j in range(10):
      for k in range(10):
        costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])
  
  min_total = INF
  best_city = -1
  for fr in city:
    total = 0
    for to in city:
      total += costs[fr][to]
    if total < min_total:
      min_total = total
      best_city = fr
  print(best_city, min_total)

Submission status: Wrong Answer

Solution code:
from itertools import product
while True:
    N = input()
    if N == 0:
        break
    g = [[2<<30 if i!=j else 0 for j in xrange(10)] for i in xrange(10)]
    n = 0
    for _ in xrange(N):
        a,b,c = map(int,raw_input().split())
        g[a][b] = g[b][a] = c
        n = max(n,a,b)
    g = [gg[:n+1] for gg in g[:n+1]]
    for i,j,k in product(xrange(n+1),repeat=3):
        g[i][j] = min(g[i][j],g[i][k]+g[k][j])
    print "{} {}".format(*min(zip(range(n),map(sum,g)),key=lambda(i,s):s))

Submission status: Wrong Answer

Solution code:
from itertools import product
while True:
    N = input()
    if N == 0:
        break
    g = [[2<<30 if i!=j else 0 for j in xrange(11)] for i in xrange(11)]
    n = 0
    for _ in xrange(N):
        a,b,c = map(int,raw_input().split())
        g[a][b] = g[b][a] = c
        n = max(n,a,b)
    g = [gg[:n+1] for gg in g[:n+1]]
    for i,j,k in product(xrange(n+1),repeat=3):
        g[i][j] = min(g[i][j],g[i][k]+g[k][j])
    print "{} {}".format(*min(zip(range(n),map(sum,g)),key=lambda(i,s):s))

Submission status: Wrong Answer

Solution code:
from itertools import product
while True:
    N = input()
    if N == 0:
        break
    g = [[2<<30 if i!=j else 0 for j in xrange(11)] for i in xrange(11)]
    n = 0
    for _ in xrange(N):
        a,b,c = map(int,raw_input().split())
        g[a][b] = g[b][a] = c
        n = max(n,a,b)
    for i,j,k in product(xrange(n+1),repeat=3):
        g[i][j] = min(g[i][j],g[i][k]+g[k][j])
    a = [sum(filter(lambda x:x<(2<<30),g[i])) for i in xrange(n+1)]
    print "{} {}".format(*min(zip(range(11),a),key=lambda(i,s):s))

Submission status: Wrong Answer

Solution code:
inf = 1e10
def solve(G,start):
	cost = [inf]*n
	visited = [False]*n
	cost[start] = 0
	min = inf
	while 1:
		visited[start] = True
		next = -1
		for i in range(n):
			if visited[i]: continue
			if G[start][i]:
				d = cost[start] + G[start][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i
		start = next
		if next == -1: break
	return cost

while 1:
	e = input()
	if e == 0: break
	road = [map(int,raw_input().split()) for i in range(e)]
	n = max(max(road[i][0],road[i][1]) for i in range(e)) + 1
	G = [[0]*n for i in range(n)]
	for s,t,d in road:
		G[s][t] = G[t][s] = d
	cost = [sum(solve(G,i)) for i in range(n)]
	print cost.index(min(cost)),min(cost)

Submission status: Wrong Answer

Solution code:
inf = 10000000
def solve(G,start):
	cost = [inf]*10
	visited = [False]*10
	cost[start] = 0
	min = inf
	while 1:
		visited[start] = True
		next = -1
		for i in range(10):
			if visited[i]: continue
			if G[start][i]:
				d = cost[start] + G[start][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i
		start = next
		if next == -1: break
	return cost

while 1:
	n = input()
	if n == 0: break
	road = [map(int,raw_input().split()) for i in range(n)]
	G = [[0]*10 for i in range(10)]
	for s,t,d in road:
		G[s][t] = G[t][s] = d
	cost = [sum(solve(G,i)) for i in range(10)]
	print cost.index(min(cost)),min(cost)%inf

Submission status: Wrong Answer

Solution code:
inf = 10000000
def solve(G,start):
	cost = [inf]*10
	visited = [False]*10
	cost[start] = 0
	min = inf
	while 1:
		visited[start] = True
		next = -1
		for i in range(10):
			if visited[i]: continue
			if G[start][i] > -1:
				d = cost[start] + G[start][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i
		start = next
		if next == -1: break
	return cost

while 1:
	n = input()
	if n == 0: break
	road = [map(int,raw_input().split()) for i in range(n)]
	G = [[-1]*10 for i in range(10)]
	for a,b,c in road:
		G[a][b] = G[a][b] = c
	cost = [sum(solve(G,i)) for i in range(10)]
	print cost.index(min(cost)),min(cost)%inf

Submission status: Wrong Answer

Solution code:
inf = 100000000
def solve(G,start):
	cost = [inf]*10
	visited = [False]*10
	cost[start] = 0
	min = inf
	while 1:
		visited[start] = True
		next = -1
		for i in range(10):
			if visited[i]: continue
			if G[start][i] > -1:
				d = cost[start] + G[start][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:
				min = cost[i]
				next = i
		start = next
		if next == -1: break
	return cost

while 1:
	n = input()
	if n == 0: break
	road = [map(int,raw_input().split()) for i in range(n)]
	G = [[-1]*10 for i in range(10)]
	for a,b,c in road:
		G[a][b] = G[b][a] = c
	cost = [sum(solve(G,i)) for i in range(10)]
	print cost.index(min(cost)),min(cost)%inf

Submission status: Accepted

Solution code:
INF = 10**10
def dijkstra(s):
    dist = [INF]*size
    used = [False]*size
    dist[s] = 0
    while 1:
        v = -1
        for u in range(size):
            if not used[u] and (v == -1 or dist[u] < dist[v]): v = u
        if v == -1: break
        used[v] = True
        for u in range(size):
            dist[u] = min(dist[u],dist[v]+G[v][u])
    return dist

while 1:
    n = int(raw_input())
    if n == 0: break
    abc = [map(int,raw_input().split()) for _ in range(n)]
    size = max(max(a,b) for a,b,c in abc)+1
    G = [[INF for _ in range(size)] for __ in range(size)]
    for a,b,c in abc:
        G[a][b] = G[b][a] = c
    sumdist = 10**10
    town = 0
    for s in range(size):
        tmp = sum(dijkstra(s))
        if tmp < sumdist:
            sumdist = tmp
            town = s
    print town,sumdist

Submission status: Accepted

Solution code:
class WarshallFloyd():
    """Warshall-Floyd Algorithm: 
       find the lengths of the shortest paths between all pairs of vertices
       used in GRL1C(AOJ), aoj0189
    """

    def __init__(self, V, E, INF=10**9):
        """ V: the number of vertexes
            E: adjacency list
            start: start vertex
            INF: Infinity distance
        """
        self.V = V
        self.E = E
        self.warshall_floyd(INF)

    def warshall_floyd(self, INF):
        self.distance = [[INF] * self.V for _ in range(self.V)]
        for i in range(self.V): self.distance[i][i] = 0
        for fr in range(self.V):
            for to, cost in self.E[fr]:
                self.distance[fr][to] = cost
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if self.distance[i][k] != INF and self.distance[k][j] != INF:
                        self.distance[i][j] = min(self.distance[i][j], self.distance[i][k] + self.distance[k][j])

    def hasNegativeCycle(self):
        for i in range(self.V):
            if self.distance[i][i] < 0:
                return True
        else:
            return False
                
while True:
    E = int(input())
    if E == 0: break
    V = 0
    edge = [[] for _ in range(10)]
    for _ in range(E):
        s, t, cost = map(int, input().split())
        V = max(s, t, V)
        edge[s].append((t, cost))
        edge[t].append((s, cost))
    allsp = WarshallFloyd(V+1, edge)
    ans = (10**9, 10**9)
    for i in range(V+1):
        ans = min(ans, (sum(allsp.distance[i]), i))
    print(*ans[::-1])

Submission status: Accepted

Solution code:
# Aizu Problem 0189: Convenient Location
#
import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")



while True:
    n = int(input())
    if n == 0:
        break
    L = []
    cities = set()
    for _ in range(n):
        city1, city2, weight = [int(_) for _ in input().split()]
        L.append([city1, city2, weight])
        cities.add(city1)
        cities.add(city2)
    m = len(cities)
    dist = [[2**31] * m for _ in range(m)]
    for i in range(m):
        dist[i][i] = 0
    for city1, city2, weight in L:
        dist[city1][city2] = weight
        dist[city2][city1] = weight
    for k in range(m):
        for i in range(m):
            for j in range(m):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    city, time = -1, 2**31
    for k in range(m):
        S = sum(dist[k])
        if S < time:
            time = S
            city = k
    print(city, time)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0189

"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])


def main(args):
    while True:
        n_max = 9+1
        n = int(input())
        if n == 0:
            break
        dp = [[float('inf')] * n_max for _ in range(n_max)]
        for i in range(n_max):
            dp[i][i] = 0

        max_town = 0
        for _ in range(n):
            a, b, c = map(int, input().split())
            dp[a][b] = c
            dp[b][a] = c
            max_town = max(max_town, a, b)

        warshallFloyd(max_town + 1, dp)


        min_dist = float('inf')
        town_live = -1
        for i, d in enumerate(dp[:max_town+1]):
            sum_dist = 0
            for ele in d[:max_town+1]:
                sum_dist += ele
            if sum_dist < min_dist:
                min_dist = sum_dist
                town_live = i

        print('{} {}'.format(town_live, min_dist))



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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0189
AC
"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp_ik = dp[i][k]
                dp_kj = dp[k][j]
                if dp[i][j] > dp_ik + dp_kj:
                    dp[i][j] = dp_ik + dp_kj


def main(args):
    while True:
        n_max = 9+1
        n = int(input())
        if n == 0:
            break
        dp = [[float('inf')] * n_max for _ in range(n_max)]
        for i in range(n_max):
            dp[i][i] = 0

        max_town = 0
        for _ in range(n):
            a, b, c = map(int, input().split())
            dp[a][b] = c
            dp[b][a] = c
            max_town = max(max_town, a, b)

        warshallFloyd(max_town + 1, dp)


        min_dist = float('inf')
        town_live = -1
        for i, d in enumerate(dp[:max_town+1]):
            sum_dist = 0
            for ele in d[:max_town+1]:
                sum_dist += ele
            if sum_dist < min_dist:
                min_dist = sum_dist
                town_live = i

        print('{} {}'.format(town_live, min_dist))



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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0189
AC
"""
import sys
from sys import stdin
input = stdin.readline


def warshallFloyd(V, dp):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dp_ik = dp[i][k]
                dp_kj = dp[k][j]
                if dp[i][j] > dp_ik + dp_kj:
                    dp[i][j] = dp_ik + dp_kj


def main(args):
    while True:
        n_max = 9+1
        n = int(input())
        if n == 0:
            break
        dp = [[float('inf')] * n_max for _ in range(n_max)]
        for i in range(n_max):
            dp[i][i] = 0

        max_town = 0
        for _ in range(n):
            a, b, c = map(int, input().split())
            dp[a][b] = c
            dp[b][a] = c
            if a > max_town:
                max_town = a
            if b > max_town:
                max_town = b

        warshallFloyd(max_town + 1, dp)


        min_dist = float('inf')
        town_live = -1
        for i, d in enumerate(dp[:max_town+1]):
            sum_dist = sum(d[:max_town+1])
            if sum_dist < min_dist:
                min_dist = sum_dist
                town_live = i

        print('{} {}'.format(town_live, min_dist))



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

Submission status: Accepted

Solution code:
from collections import defaultdict
road = int(input())
while road > 0:
    connect = defaultdict(list)
    # weight = defaultdict(defaultdict(float("inf")))
    answer = [[float("inf") if n != m else 0 for n in range(10)] for m in range(10)]
    for _ in range(road):
        c1, c2, w = (int(n) for n in input().split(" "))
        connect[c1].append(c2)
        connect[c2].append(c1)
        answer[c1][c2] = w
        answer[c2][c1] = w
    city = max(connect.keys()) + 1
    for i in range(city):
        for j in range(city):
            for k in range(city):
                answer[j][k] = min(answer[j][k], answer[j][i] + answer[i][k])
    sum_ans = [-1 , float("inf")]
    for i in range(city):
        if sum(answer[i][:city]) < sum_ans[1]:
            sum_ans = [i, sum(answer[i][:city])]
    print(*sum_ans)
    road = int(input())

Submission status: Accepted

Solution code:
road = int(input())
while road > 0:
    answer = [[float("inf") if n != m else 0 for n in range(10)] for m in range(10)]
    city = 0
    for _ in range(road):
        c1, c2, w = (int(n) for n in input().split(" "))
        answer[c1][c2] = w
        answer[c2][c1] = w
        city = max(city, c1, c2)
    city += 1
    for i in range(city):
        for j in range(city):
            for k in range(city):
                answer[j][k] = min(answer[j][k], answer[j][i] + answer[i][k])
    sum_ans = [-1 , float("inf")]
    for i in range(city):
        if sum(answer[i][:city]) < sum_ans[1]:
            sum_ans = [i, sum(answer[i][:city])]
    print(*sum_ans)
    road = int(input())

Submission status: Accepted

Solution code:
import sys
from sys import stdin
input = stdin.readline

road = int(input())
while road > 0:
    answer = [[float("inf") if n != m else 0 for n in range(10)] for m in range(10)]
    city = 0
    for _ in range(road):
        c1, c2, w = (int(n) for n in input().split(" "))
        answer[c1][c2] = w
        answer[c2][c1] = w
        city = max(city, c1, c2)
    city += 1
    for i in range(city):
        for j in range(city):
            for k in range(city):
                answer[j][k] = min(answer[j][k], answer[j][i] + answer[i][k])
    sum_ans = [-1 , float("inf")]
    for i in range(city):
        if sum(answer[i][:city]) < sum_ans[1]:
            sum_ans = [i, sum(answer[i][:city])]
    print(*sum_ans)
    road = int(input())

Submission status: Accepted

Solution code:
NULL = 10000
TOWN_COUNT = 10

while True:

    input_count = int(input())

    if input_count == 0:
        break

    adjacency_matrix = [[NULL] * TOWN_COUNT for _ in range(TOWN_COUNT)]

    for lp in range(TOWN_COUNT):
        adjacency_matrix[lp][lp] = 0

    need_range = 0

    for _ in range(input_count):
        start, end, time = [int(item) for item in input().split(" ")]

        adjacency_matrix[start][end] = time
        adjacency_matrix[end][start] = time

        need_range = max(need_range, start, end)

    for a in range(need_range + 1):
        for b in range(need_range + 1):
            for c in range(need_range + 1):
                adjacency_matrix[b][c] = min(adjacency_matrix[b][a] + adjacency_matrix[a][c], adjacency_matrix[b][c])

    min_time = NULL
    min_index = -1

    for index, item in enumerate(adjacency_matrix):
        need_element = [item2 for item2 in item if 0 < item2 < NULL]

        if 0 < len(need_element):
            time = sum(need_element)

            if time < min_time:
                min_time = time
                min_index = index

    print(min_index, min_time)

Submission status: Accepted

Solution code:
INF = 10 ** 10
while True:
  n = int(input())
  if n == 0:
    break

  costs = [[INF] * 10 for _ in range(10)]
  for i in range(10):
    costs[i][i] = 0
  
  city = set()
  for _ in range(n):
    a, b, c = map(int, input().split())
    city = city | {a, b}
    costs[a][b] = c
    costs[b][a] = c 
  
  city = sorted(list(city))
  
  for k in range(10):
    for i in range(10):
      for j in range(10):
        costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])
  
  min_total = INF
  best_city = -1
  for fr in city:
    total = 0
    for to in city:
      total += costs[fr][to]
    if total < min_total:
      min_total = total
      best_city = fr
  print(best_city, min_total)

Submission status: Accepted

Solution code:
INF=1e100000
while True:
    n=input()
    if n==0:break
    S=set()
    L=[]
    for i in range(n):
        a,b,c=map(int,raw_input().split())
        L.append((a,b,c))
        S.add(a)
        S.add(b)
    m=len(S)
    R=[[INF]*m for i in range(m)]
    for i in range(m):
        R[i][i]=0
    for a,b,c in L:
        R[a][b]=c
        R[b][a]=c
    for k in range(m):
        for i in range(m):
            for j in range(m):
                R[i][j]=min(R[i][j],R[i][k]+R[k][j])
    city,time=-1,INF
    for i in range(m):
        s=sum(R[i])
        if s<time:
            city=i
            time=s
    print city,time

Submission status: Accepted

Solution code:
from itertools import product
while True:
    N = input()
    if N == 0:
        break
    g = [[2<<30 if i!=j else 0 for j in xrange(11)] for i in xrange(11)]
    used = [False]*11
    for _ in xrange(N):
        a,b,c = map(int,raw_input().split())
        g[a][b] = g[b][a] = c
        used[a] = used[b] = True
    for k,i,j in product(xrange(11),repeat=3):
        g[i][j] = min(g[i][j],g[i][k]+g[k][j])
    a = [sum(filter(lambda x:x<(2<<30),g[i])) if used[i] else 2<<30 for i in xrange(11)]
    print "{} {}".format(*min(zip(range(11),a),key=lambda(i,s):s))

Submission status: Accepted

Solution code:
from itertools import product
INF = 2<<30
while True:
    N = input()
    if N == 0:
        break
    g = [[INF if i!=j else 0 for j in xrange(11)] for i in xrange(11)]
    used = [False]*11
    for _ in xrange(N):
        a,b,c = map(int,raw_input().split())
        g[a][b] = g[b][a] = c
        used[a] = used[b] = True
    for k,i,j in product(xrange(11),repeat=3):
        g[i][j] = min(g[i][j],g[i][k]+g[k][j])
    a = [sum(filter(lambda x:x<(INF),g[i])) if used[i] else INF for i in xrange(11)]
    print "{} {}".format(*min(zip(range(11),a),key=lambda(i,s):s))

Submission status: Accepted

Solution code:
num_of_path = int(input())

while num_of_path != 0:
	inf = 1e8
	data = []
	num_of_cities = 0
	for _ in range(num_of_path):
		add_data = list(map(int,input().split()))
		data.append(add_data)
		if num_of_cities < max(add_data[0],add_data[1]):
			num_of_cities = max(add_data[0],add_data[1])

	num_of_cities += 1
	w = [[1e8]*num_of_cities for i in range(num_of_cities)]
	for d in data:
		w[d[0]][d[1]] = d[2]
		w[d[1]][d[0]] = d[2]


	for k in range(num_of_cities):
		for j in range(num_of_cities):
			for i in range(num_of_cities):
				w[i][j] = min(w[i][j],w[i][k]+w[k][j])

	for i,row in zip(range(num_of_cities),w):
		row[i] = 0		

	s = [sum(w[i]) for i in range(num_of_cities)]
	print(f"{s.index(min(s))} {min(s)}")

	num_of_path = int(input())

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

INF = 10**9
def solve():
    N = int(readline())
    if N == 0:
        return False
    K = 0
    E = [[INF]*10 for i in range(10)]
    for i in range(N):
        a, b, c = map(int, readline().split())
        E[a][b] = E[b][a] = c
        K = max(K, a+1, b+1)
    for i in range(K):
        E[i][i] = 0
    for k in range(K):
        for i in range(K):
            for j in range(K):
                E[i][j] = min(E[i][j], E[i][k] + E[k][j])
    k = -1; s = INF
    for i in range(K):
        Ei = E[i]
        v = sum(Ei[j] for j in range(K) if Ei[j] < INF)
        if v < s:
            s = v; k = i
    write("%d %d\n" % (k, s))
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect
import heapq

MOD = float('inf')
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()


def warshall_floyd(d):
    """
    d[i][l]がi→lへのコストを示す隣接行列
    結果としてd[i][l]はi→lへの最短コストになる。
    """
    for i in range(len(d)):
        for l in range(len(d)):
            for k in range(len(d)):
                d[l][k] = min(d[l][k], d[l][i] + d[i][k])
    return d


while True:
    n = int(input())
    if n == 0:
        break
    else:
        abc = [list(map(int, input().split())) for _ in range(n)]
        info = [[INF for _ in range(10)] for _ in range(10)]
        for i in range(10):
            info[i][i] = 0
        for i in abc:
            info[i[0]][i[1]] = i[2]
            info[i[1]][i[0]] = i[2]
        result = warshall_floyd(info)
        ans = []
        for i in result:
            for l in range(len(i)):
                if i[l] == INF:
                    i[l] = 0
        for i in range(10):
            if sum(result[i]) != 0:
                ans.append([sum(result[i]), i])
        ans.sort()
        print(ans[0][1], ans[0][0])

Submission status: Accepted

Solution code:
while True:
    N = int(input())
    if N == 0:
        break

    abc = []
    cities = [False] * 10
    for i in range(N):
        a, b, c = list(map(int, input().split()))
        cities[a] = True
        cities[b] = True
        abc.append([a, b, c])

    cnum = cities.count(True)

    # G[i][j]: iとjの最短経路
    G = []
    for i in range(cnum):
        a = [float('inf')] * cnum
        G.append(a)

    for i in range(cnum):
        G[i][i] = 0

    for a, b, c in abc:
        G[a][b] = min(G[a][b], c)
        G[b][a] = min(G[b][a], c)


    for k in range(cnum):
        for i in range(cnum):
            for j in range(cnum):
                G[i][j] = min(G[i][j], G[i][k] + G[k][j])

    # for i in range(cnum):
    #     print(G[i])
    min_city = None
    min_cost = float('INF')
    for i in range(cnum):
        c = sum(G[i])
        if c < min_cost:
            min_cost = c
            min_city = i

    print(min_city, min_cost)

Submission status: Accepted

Solution code:
def floyd_warshall(d):
    v = len(d)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

while True:
    n = int(input())
    if n == 0:
        break
    info = []
    num_cities = 1
    for i in range(n):
        a, b, c = map(int, input().split())
        num_cities = max(num_cities, a+1, b+1)
        info.append((a, b, c))

    d = [[0 if i == j else float('inf') for j in range(num_cities)] for i in range(num_cities)]
    for a, b, c in info:
        d[a][b] = d[b][a] = c

    floyd_warshall(d)
    total = [sum(d[i]) for i in range(num_cities)]
    min_dist = min(total)
    print(total.index(min_dist), min_dist)

Submission status: Accepted

Solution code:
INF = float('inf')
TOWN_NUM = 10

while True:
    way_num = int(input())
    if way_num == 0:
        break

    table = [[INF for i in range(TOWN_NUM)] for j in range(TOWN_NUM)]

    for _ in range(way_num):
        a,b,c = [int(i) for i in input().split()]
        table[a][b] = c
        table[b][a] = c

    for k in range(TOWN_NUM):
        for i in range(TOWN_NUM):
            for j in range(TOWN_NUM):
                if table[i][j] > table[i][k] + table[k][j]:
                    table[i][j] = table[i][k] + table[k][j]

    answer = INF
    answer_id = 0
    for i in range(TOWN_NUM):
        tmp = 0
        flag = False
        for j in range(TOWN_NUM):
            if table[i][j] < INF and i != j:
                tmp = tmp + table[i][j]
                flag = True
        if tmp < answer and flag:
            answer = tmp
            answer_id = i

    print(answer_id, answer)

Submission status: Accepted

Solution code:
INF = 10000000

while True:
    n = int(input())
    if n == 0:
        break
    
    table = [[INF for i in range(10)] for j in range(10)]
    
    for l in range(n):
        a,b,c = [int(i) for i in input().split()]
        table[a][b] = c
        table[b][a] = c
        

    for k in range(10):
        for i in range(10):
            for j in range(10):
                if table[i][j] > table[i][k] + table[k][j]:
                    table[i][j] = table[i][k] + table[k][j]

    ans = INF
    ansid = 0
    for i in range(10):
        tmp = 0
        flag = False
        for j in range(10):
            if table[i][j] < INF and i != j:
                tmp = tmp + table[i][j]
                flag = True
        if tmp < ans and flag:
            ans = tmp
            ansid = i

    print(ansid,ans)