백준 #11404 플로이드 (파이썬)

문제 링크

현재 백준 문제집: 단기간 성장을 풀고 있습니다.

생각할 것도 없고, 그냥 플로이드-워셜 알고리즘을 쓰기만 하면 통과할 수 있다.

다만, 이 문제에서만 해당하는 특수한 조건이 몇 가지 있다.

1. 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

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

2. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다.
   만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

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

기본 플로이드-워셜 알고리즘에 위의 코드를 추가하였다.

풀이

import sys
INF = int(1e9)

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
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, sys.stdin.readline().rstrip().split())
    graph[a][b] = min(graph[a][b], c)
    
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:
            graph[i][j] = 0
for i in range(1, n+1):
    print(' '.join(map(str, graph[i][1:])))