백준 11404 플로이드

25.21m

나의 답

import sys
input = sys.stdin.readline
INF = sys.maxsize

n = int(input().rstrip())
m = int(input().rstrip())
bus = [[INF] * n for _ in range(n)]

for _ in range(m):
    a, b, c = list(map(int, input().rstrip().split()))
    bus[a - 1][b - 1] = min(c, bus[a - 1][b - 1])

for k in range(n): #거치는 점
    for i in range(n): #시작 점
        for j in range(n): #끝 점
            if i == j:
                bus[i][j] = 0
                continue
            bus[i][j] = min(bus[i][k] + bus[k][j], bus[i][j])

for row in bus:
    for el in row:
        if el >= INF: print(0, end=' ')
        else: print(el, end=' ')
    print()

아 훨씬 짧게 풀 수 있었는데...
시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.
이거를 그냥 플로이드워셜 느낌으로 환승해서 이어질 수 있다는 말로 알아들었다.
알고보니 그냥 같은 노선의 더 저렴한 버스가 있을 수 있다는 뜻이었고...
백준은 가끔 이렇게 아리송한 문장으로 시간 낭비하게 만든ㄷㅏ..

여튼 플로이드워셜로 풀면 쉽게 풀린다!