INF float inf int input list map int input split for in range for in r

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
INF = float('inf')
N = int(input())
W = [list(map(int, input().split())) for i in range(N)]
for i in range(N):
for j in range(N):
if W[i][j] == 0:W[i][j] = INF
for g in range(N-1):
n = g + 1
active = [True] * N
R = W[n - 1][:]
P = [n - 1] * N
active[n - 1] = False
P[n - 1] = -1
kMin = -1
for i in range(N - 1):
minDist = INF
for j in range(N):
if active[j] and R[j] < minDist:
minDist = R[j]
kMin = j
if kMin != -1:
active[kMin] = False
for j in range(N):
if R[kMin] + W[kMin][j] < R[j]:
R[j] = R[kMin] + W[kMin][j]
P[j] = kMin
for i in range(g+1,N):
m = i + 1
print('(' + str(n) + ',' + str(m) + '):', end=" ")
if R[m - 1] != INF:
i = m - 1
a = []
while i != n - 1:
i = P[i]
a = [i + 1] + a
a = a + [m]
for i in range(len(a)):
print(a[i], end=" ")
print('(' + str(R[m - 1]) + ')')
else:
print(0)