[알고리즘] 백준11404 플로이드 - 파이썬

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

11404번: 플로이드

 

 

[풀이 코드]

from sys import stdin

input = stdin.readline

n = int(input()) # 도시의 개수
m = int(input()) # 버스의 개수
INF = int(1e9)
graph = [[INF] * (n+1) for _ in range(n+1)]

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

for _ 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 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: #만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.
            print(0, end=' ')
        else:
            print(graph[i][j], end=' ')
    print()

- 모든 노드에서 다른 모든 =노드까지의 최단경로를 모두 계산하는 플로이드-워셜 알고리즘을 활용하면 풀 수 있는 문제이다.  Dab = min(Dab, Dak + Dkb) 점화식을 활용하면 된다.

 

- 이 문제에서 주의할 점은 제약조건을 잘 파악해야 했다. 예제 입력을 보면 1 4 1, 1 4 2 두 가지의 경우가 있는데 이때는 1 4 1이 더 최소의 경우니까 이를 저장해야 한다. 문제에는 "시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다."라고 표기되어있다. 

 

- 출력에는 i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력하라는 조건이 있다. 이 부분은 주석에 넣어놨다.