백준 1238번 파이썬 문제풀이(파티)

---

단순히 해당 문제를 풀려면 우선 X지점부터 각지점까지의 최단거리를 다익스트라로 구하고 그 후에 반복문을 돌며 각 지점에서 X까지 다익스트라로 최단거리를 구해서 그 2개의 합의 최댓값을 구하면 된다.

 

그러나 해당문제를 다익스트라 2번으로 굉장히 빠르게 풀 수 있는 방법이 있다. 바로 "각 지점에서 X까지 다익스트라로 최단거리를 구해서" 이부분을 단순히 그래프를 처음 입력받을 때 간선을 반대로 저장해놓으면 한번의 다익스트라로 모든 최단거리를 구할 수 있다. 즉, 반대로 뒤집어진 그래프에서 X지점에서 각지점까지의 최단거리가 결국 "각 지점에서 X까지 다익스트라로 최단거리" 가 되는 것이다.

 

import heapq
import sys

input = sys.stdin.readline


def dijkstra(s, graph: list, distance: list):
    q = []
    heapq.heappush(q, (0, s))
    distance[s] = 0
    while q:
        cost, cur = heapq.heappop(q)

        if distance[cur] < cost:
            continue

        for nxt, nxt_cost in graph[cur]:
            if distance[nxt] > nxt_cost + cost:
                distance[nxt] = nxt_cost + cost
                heapq.heappush(q, (distance[nxt], nxt))


N, M, X = map(int, input().split())

graph = [[] for _ in range(N + 1)]
graph_r = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b, cost = map(int, input().split())
    graph[a].append((b, cost))
    graph_r[b].append((a, cost))

distance_r = [1e10] * (N + 1)
dijkstra(X, graph_r, distance_r)

distance = [1e10] * (N + 1)
dijkstra(X, graph, distance)

ans = 0
for i in range(1, N + 1):
    ans = max(ans, distance[i] + distance_r[i])

print(ans)