1238번 파티

문제

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

접근 방식

✨reverse dijkstra✨는 처음이라 기록하는 TIL이 아닌 YIL (Yesterday-I-Learned 🙄)

여기서는 각각의 위치에서 목적지 X까지 갔다가 + 오는 최단 거리가 가장 긴 경우를 골라야한다. 모든 지점에서 다른 모든 지점까지의 경로를 구하기 위해서는 플로이드 워셜이 가장 먼저 떠오르는데, 여기서는 N의 범위가 1 ≤ N ≤ 1,000 이렇게 되기 때문에 dp 테이블을 만드는 과정이 1000 * 1000 * 1000만큼의 시간복잡도가 걸려서 통과하기 어려울 것이다.

그러면 차순위로 생각나는 건 특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 구하는 다익스트라인데, n-1개의 k 노드에서 목적지 x까지 갔다가, x에서 다시 k 노드로 돌아가는 경우를 계산하기 위해서는 어떻게 해야 할까 ??

x -> k 돌아가는 경우는 다익스트라를 한번 돌리면 되므로 생각하기 쉽다. 문제는 n - 1개의 k -> x로 가는 경우인데, 이때는 주어진 그래프 방향성을 반대로 돌려서 x -> k로 가는 경우를 계산하는 reverse dijkstra를 활용하면 총 두 번의 다익스트라로 경로를 구할 수 있다.

코드

from heapq import heappop, heappush
import sys
input = sys.stdin.readline
INF = int(1e9)

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

forward = [[] for _ in range(n + 1)]
backward = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b, t = map(int, input().split())
    forward[a].append((b, t))
    backward[b].append((a, t))

# 목적지 x에서 각각의 점까지 최단거리
dist_f, dist_b = [INF] * (n + 1), [INF] * (n + 1)


def dijkstra_reverse(start):
    queue = []
    heappush(queue, (0, start))
    dist_b[start] = 0
    while queue:
        d, k = heappop(queue)
        if dist_b[k] < d:
            continue
        for b, c in backward[k]:
            nd = d + c
            if nd < dist_b[b]:
                dist_b[b] = nd
                heappush(queue, (nd, b))


def dijkstra(start):
    queue = []
    heappush(queue, (0, start))
    dist_f[start] = 0
    while queue:
        d, k = heappop(queue)
        if dist_f[k] < d:
            continue
        for b, c in forward[k]:
            nd = d + c
            if nd < dist_f[b]:
                dist_f[b] = nd
                heappush(queue, (nd, b))


# 출발지에서 목적지까지 -> 역방향 다익스트라
dijkstra_reverse(x)

# 목적지에서 출발지까지 -> 정방향 다익스트라
dijkstra(x)


maxDist = 0
for d1, d2 in zip(dist_b[1:], dist_f[1:]):
    maxDist = max(maxDist, d1 + d2)

print(maxDist)

👉 여기서 forward는 정방향 그래프, backward는 역방향 그래프, dist_f, dist_b는 정방향 최단 경로, 역방향 최단 경로다