[플로이드와샬] 11404번_플로이드

(2022년 7월 14일 최초 작성)

그것이 플로이드 워샬 문제입니다.

문제의 기본 아이디어는 다음과 같습니다.

다른 곳을 지날 때 A에서 B로 직진하지 않고 A에서 B로 갈 때(K)

비용이 더 낮으면 인접 행렬을 해당 비용으로 업데이트합니다.

그러면 이런 표현이 나오죠

비용(A, B) = 최소(비용(A,B), 비용(A, K) + 비용(K, B))

따라서 삼중반복문으로 풀어야 할 문제이다.

각 지점에서 각 지점까지의 비용을 찾아야 하기 때문입니다.

시간 복잡도는 O(n^3)입니다.

import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = int(input()), int(input())
graph = (((INF) * (n + 1)) for _ in range(n + 1))
for i 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):
            if a == b:
                graph(a)(b) = 0
            else:
                graph(a)(b) = min(graph(a)(b), graph(a)(k) + graph(k)(b))

for x in range(1, n + 1):
    for y in range(1, n + 1):
        if graph(x)(y) == INF:
            print(0, end = ' ')
        else:
            print(graph(x)(y), end = ' ')
    print()

==========================================

(리뷰 2023-03-04)

Floyd Warhall의 근본적인 문제인데, 문제는 공식처럼 기억해야 하는 알고리즘입니다.

시간복잡도는 O(N^3)이지만 조건에서 지정한 N의 범위가 작을 때는 최단 거리 문제를 푸는 것이 가장 편리하다.

이것은 어떤 지점에서 어떤 지점까지의 거리를 볼 수 있기 때문에 좋은 알고리즘입니다.

아래에서 해결!

import sys
input = sys.stdin.readline
INF = int(1e9)

n = int(input())
m = int(input())
graph = ((INF) * (n + 1) for _ in range(n + 1))

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

for i in range(1, n + 1):
    graph(i)(i) = 0

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 x in range(1, n + 1):
    for y in range(1, n + 1):
        print(graph(x)(y) if graph(x)(y) != INF else 0, end = ' ')
    print()

코드가 조금 더 깔끔한 느낌입니다.