[Python/파이썬] 백준 1238. 파티

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

import sys
import heapq

input = sys.stdin.readline

def dijkstra(start, graph, n):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        cost, now = heapq.heappop(heap)
        if cost > dist[now]:
            continue

        for nxt, w in graph[now]:
            if dist[nxt] > cost + w:
                dist[nxt] = cost + w
                heapq.heappush(heap, (dist[nxt], nxt))
    return dist


n, m, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]
reverse_graph = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
    reverse_graph[v].append((u, w))  # 경로를 뒤집어 파티장에서 집으로 가는 경로 계산

# 각 학생이 파티장(X)으로 가는 최단 경로
dist_to_x = dijkstra(x, reverse_graph, n)

# 파티장에서 각 학생의 집으로 돌아오는 최단 경로
dist_from_x = dijkstra(x, graph, n)

max_time = 0
for i in range(1, n + 1):
    max_time = max(max_time, dist_to_x[i] + dist_from_x[i])

print(max_time)