[백준 1238] 파티 (python)

1238번: 파티

---

다익스트라 알고리즘을 사용한다. 파티를 갔다가 와야하므로 정방향과 역방향 그래프 두개의 합을 계산해준다.

1. 가는길 goarr, 오는길 comearr에 경로들을 저장한다.
2. 가는데 걸리는 시간을 저장하는 time 배열을 생성한다.
3. queue에 시작점을 넣어준다.
4. 시작점에서 뻗을 수 있는 것들 중 저장되어 있는 것보다 더 작은 경로라면 update해주고 queue에 넣는다.
5. 두 결과값을 더해서 큰값을 구해준다.

import sys
import heapq
input = sys.stdin.readline


def dijkstra(arr, start):
    queue = [[0, start]]
    time = [sys.maxsize]*(N+1)
    time[start] = 0
    while queue:
        t, s = heapq.heappop(queue)
        for v, e in arr[s]:
            if time[e] > t+v:
                time[e] = t+v
                heapq.heappush(queue, [t+v, e])
    return time


N, M, X = map(int, input().split())
comearr = [[] for _ in range(N+1)]
goarr = [[] for _ in range(N+1)]
queue = []
for _ in range(M):
    s, e, t = map(int, input().split())
    goarr[s].append([t, e])
    comearr[e].append([t, s])

answer = 0
for i in range(1, N+1):
    come = dijkstra(comearr, X)
    go = dijkstra(goarr, X)
    answer = max(come[i] + go[i], answer)

print(answer)