[백준 파이썬] 11404 플로이드

 

11404번: 플로이드

문제

 

---

풀이

그래프의 모든 지점에 대해 최소비용을 구하는 문제이므로 플로이드를 사용하였다.

플로이드의 구현 코드는 아래와 같다.

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])

 

그래프의 두 지점에 대해 두 지점을 거쳐가는 모든 경우의 최소값을 구해준다.

 

 

---

코드

import sys
INF = sys.maxsize
n = int(input())

m = int(input())

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for a in range(1, n + 1):
  for b in range(1, n + a):
    if a == b:
      graph[a][b] = 0

for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a][b] = min(c, graph[a][b])

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])

for i in range(1, n + 1):
  for j in range(1, n + 1):
    if graph[i][j] == INF:
      print(0, end=" ")
    else:
      print(graph[i][j], end=" ")
  print()