백준 #1238 #Python

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

모든 노드에서 X로, X에서 모든 노드의 최단거리를 구하는 문제입니다.

a, b, t가 주어지고 그래프를 만들 때
a -> b 의 방향으로 그래프를 만들면 X에서 모든 노드까지 최단 거리를 구할 수 있고
b -> a 의 방향으로 그래프를 만들면 모든 노드에서 X까지의 최단 거리를 구할 수 있습니다.

두 번의 다익스트라로 풀어야 시간 안에 해결할 수 있습니다.

import sys
from heapq import heappop, heappush

input = sys.stdin.readline

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

take1 = [100001]*(n+1)  // X에서 모든 노드
que = [(0, x)]
while que:
    time, now = heappop(que)
    if take1[now] <= time: continue
    take1[now] = time
    for city, t in graph1[now]:
        heappush(que, (time+t, city))

take2 = [100001]*(n+1)  // 모든 노드에서 X
que = [(0, x)]
while que:
    time, now = heappop(que)
    if take2[now] <= time: continue
    take2[now] = time
    for city, t in graph2[now]:
        heappush(que, (time+t, city))
        
ans = 0
for i in range(1, n+1):
    ans = max(ans, take1[i]+take2[i])
print(ans)