알고리즘 문제/알고리즘 노트

플로이드워셜

태윤2 2020. 10. 27. 21:10
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
# 플로이드워셜
 
INF = int(1e9)
 
n,m = map(int,input().split())
 
 
graph = [[INF]*(n+1) for _ in range(n+1)]
 
 
for i in range(m):
  a,b,c = map(int,input().split())
  if graph[a][b] > c:
    graph[a][b] = c
 
for k in range(1,n+1):
  for i in range(1,n+1):
    for j in range(1,n+1):
      graph[i][j] = min(graph[i][j],graph[i][k]+graph[k][j])
 
 
result= INF
for i in range(1,n+1):
  for j in range(1,n+1):
    result = min(result,graph[i][j]+graph[j][i])
print(result if result!=INF else -1)
 cs