[백준] 11404. 플로이드/Python - Gold4

❓문제

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

성능 요약

메모리: 111660 KB, 시간: 164 ms

분류

그래프 이론, 최단 경로, 플로이드–워셜

문제 설명

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

✍🏻풀이

플로이드 워셜 알고리즘을 구현하면 된다.

a에서 b로 가는데 중간에 다른 도시를 경유하는 경우와 한 번에 가는 경우 중 가중치가 최소인 경우를 기록하면 된다.

가중치 계산이 끝나고 출력할 때 a에서 b로 갈 수 없는 곳은 0으로 출력해야 한다.

💻코드

import sys

input = sys.stdin.readline

# n = bus(vertex), m = busline(edge)
n = int(input())
m = int(input())
INF = 1e9
cities = [[0 if a == b else INF for b in range(n)] for a in range(n)]

for _ in range(m):
    a, b, c = map(int, input().split())
    cities[a-1][b-1] = min(cities[a-1][b-1], c)
    
for k in range(n):
    for a in range(n):
        for b in range(n):
            cities[a][b] = min(cities[a][b], cities[a][k] + cities[k][b])
                
for a in range(n):
    for b in range(n):
        print(0 if cities[a][b] == INF else cities[a][b], end=' ')
    print()

📍후기

출력부분을 제대로 안 읽어서 계속 틀렸다가 맞았다...