[백준] 11404. 플로이드

 

📌문제

11404번: 플로이드

 

🎖️난이도

 

✔️풀이

import sys
input = sys.stdin.readline
INF = int(1e9)

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

for i in range(1, n+1):
    graph[i][i] = 0
    
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a][b] = min(c, graph[a][b]) # 연결 노선 1개 이상일 수도!!!

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

 

🧠노트

all pairs 문제이므로 DP를 이용해서 플로이드-워셜 알고리즘으로 풀이하면 된다.

 

이때,

입력부에서 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다." 이 부분이 함정이다!!

따라서 두 도시 사이의 노선이 여러 개가 주어지더라도 최솟값(min)을 비교해서 저장해줘야 한다.

 

🔍참고

-