알고리즘: 백준 1238번 파티 (feat. python)

 

1238번: 파티

 

 

import sys
import heapq
read = sys.stdin.readline
N, M, X = map(int, read().split())
graph = {i: []for i in range(1, N+1)}  # 각 마을에서 X로 가는 방향 그래프
graph2 = {i: []for i in range(1, N+1)}  # X에서 각 마을로 가는 그래프
for _ in range(M):
    s, e, l = map(int, read().split())
    graph[e].append([s, l])
    graph2[s].append([e, l])
INF = sys.maxsize
dist = [0] + [INF for _ in range(N)]
dist[X] = 0
hq = []

heapq.heappush(hq, [0, X])

while hq:
    c_w, c_n = heapq.heappop(hq)
    for n_n, n_w in graph[c_n]:
        before_weight = c_w + n_w
        if before_weight < dist[n_n]:
            dist[n_n] = before_weight
            heapq.heappush(hq, [before_weight, n_n])
            
            
dist2 = [0] + [INF for _ in range(N)]
dist2[X] = 0
hq2 = []
heapq.heappush(hq2, [0, X])
while hq2:
    c_w, c_n = heapq.heappop(hq2)
    for n_n, n_w in graph2[c_n]:
        before_weight = c_w + n_w
        if before_weight < dist2[n_n]:
            dist2[n_n] = before_weight
            heapq.heappush(hq2, [before_weight, n_n])
            
max_value = 0
for i in range(1, N+1):
    if max_value < dist[i] + dist2[i]:
        max_value = dist[i] + dist2[i]
print(max_value)