백준 11404 플로이드 (Python)

문제 링크

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

11404번: 플로이드

---

Test Case

---

문제 풀이

모든 점에서 모든 점으로 가는 최소값을 구하는 문제. 문제를 읽고 제목을 보지않더라도 바로 플로이드 문제인걸 알아야한다.
그닥 특이점은 없지만 문제 마지막줄에 '시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.' 라는 점과 예제에서 3 -> 4 정보가 두개라는 점에서 graph[a][b] = min(graph[a][b], c) 만 신경쓰면 된다.
플로이드 와샬 문제라는 것을 빨리 파악하는 것이 포인트

---

Source Code

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(n+1):
    for j in range(n+1):
        if i==j :
            graph[i][j] = 0
for i in range(m):
    a,b,c = map(int, input().split())
    graph[a][b] = min(graph[a][b], c)

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

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