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

 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
INF = float('inf')
n, m = map(int, input().split())
W = [[INF]*n for i in range(n)]
for i in range(n): W[i][i] = 0
for i in range(m):
r = list(map(int, input().split()))
if W[r[0]-1][r[1]-1] > r[2]:
W[r[0]-1][r[1]-1] = r[2]
W[r[1]-1][r[0]-1] = r[2]
color = [i for i in range(n)]
ostov = []
for k in range(n-1):
minDist = INF
for i in range(n):
for j in range(n):
if color[i] != color[j] and W[i][j] < minDist:
iMin = i
jMin = j
minDist = W[i][j]
ostov.append ( (iMin+1, jMin+1) )
c = color[jMin]
for i in range(n):
if color[i] == c:
color[i] = color[iMin]
sum = 0
for rebro in ostov:
sum += W[rebro[0]-1][rebro[1]-1]
print(sum)