[파이썬] 백준 11404 : 플로이드 (골드4)

[파이썬] 백준 11404 : 플로이드 (골드4)

• https://www.acmicpc.net/problem/11404
  

---

풀이

방향성 생각

• a에서 b로가는 간선정보가 다수 들어올 수 있으니, 최소값을 그래프에 저장해준다.
• 이후 플로이드워셜로 풀이

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

N = int(input())

G = [[1e9]*(N+1) for _ in range(N+1)]
for _ in range(int(input())):
    a,b,cost = map(int,input().split())
    G[a][b] = min(G[a][b],cost)

for i in range(1,N+1):
    G[i][i] = 0

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if G[i][k] + G[k][j] < G[i][j]:
                G[i][j] = G[i][k] + G[k][j]

for i in range(1,N+1):
    for j in range(1,N+1):
        print(0 if G[i][j] == 1e9 else G[i][j],end=' ')
    print()

코멘트

• .