파티 - BOJ

파티 - BOJ

import heapq

def di(n, d, dist):
    li = []
    heapq.heappush(li, (0, n))
    dist[n] = 0
    while li:
        cost, edge = heapq.heappop(li)
        for i in d[edge]:
            other = cost + i[1]
            if dist[i[0]] > other:
                dist[i[0]] = other
                heapq.heappush(li, (other, i[0]))
    return dist

N, M, X = map(int, input().split())
d1 = [[] for _ in range(N + 1)]
d2 = [[] for _ in range(N + 1)]

inf = float('inf')
dist1 = [inf] * (N + 1)
dist2 = [inf] * (N + 1)

for i in range(M):
    s, e, t = map(int, input().split())
    d1[s].append((e, t))
    d2[e].append((s, t))

ret1 = di(X, d1, dist1)
ret2 = di(X, d2, dist2)
ret = 0
for i in range(1, N + 1):
    if ret1[i] != inf and ret2[i] != inf:
        ret = max(ret, ret1[i] + ret2[i])
print(ret)