BOJ - 1238 - 파티

import sys
from heapq import heappush, heappop

def Dijkstra(start, graph, V):
    heap = []
    distance = [1e9] * (V +1)
    distance[start] = 0
    heappush(heap, (0, start))

    while heap:
        weight, location = heappop(heap)

        if distance[location] < weight:
            continue

        for l, w in graph[location]:
            w += weight
            if w < distance[l]:
                distance[l] = w
                heappush(heap, (w, l))

    return distance

def solution():
    N, M, X = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N + 1)]
    reversegraph = [[] for _ in range(N + 1)]

    for _ in range(M):
        u, v, w = map(int, sys.stdin.readline().split())
        graph[u].append([v, w])
        reversegraph[v].append([u, w])

    ret = Dijkstra(X, graph, N)
    reverseret = Dijkstra(X, reversegraph, N)

    dist = 0
    for i in range(1, N+1):
        dist = max(dist, (reverseret[i] + ret[i]))
    print(dist)

solution()

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