[백준 1719] 택배 (Gold 3)

문제

[백준] 택배 (Gold 3)

요약

택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하는지 아래와 같은 경로표로 정리하라. 경로표는 한 집하장에서 다른 집하장으로 최단경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타낸 것이다.

분류

• 다익스트라
• 플로이드 워셜

풀이

1. 내 풀이 (플로이드 워셜)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

inters = [["-"] * n for _ in range(n)]  # 최단거리 경로 번호표
fw = [[sys.maxsize] * n for _ in range(n)]  # 최단거리 표

for _ in range(m):
    a, b, time = map(int, input().split())

    fw[a - 1][b - 1] = time
    fw[b - 1][a - 1] = time
    inters[a - 1][b - 1] = b
    inters[b - 1][a - 1] = a

for inter in range(n):
    for r in range(n):
        for c in range(n):
            if r == c or r == inter or c == inter:
                continue

            if fw[r][c] > fw[r][inter] + fw[inter][c]:
                fw[r][c] = fw[r][inter] + fw[inter][c]
                inters[r][c] = inters[r][inter] if inters[r][inter] != "-" else inter + 1

for i in inters:
    print(*i)

2. 다익스트라

링크