[ 1238 ] [ Dijkstra ] 파티

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

1238번: 파티

 

 

---

풀이 과정

---

1. 단방향 그래프이므로 시작점을 X를 제외한 모든 점에서 다익스트라 알고리즘을 진행해보아야 한다.
   1. 시작하기 전에, X점에서 다익스트라 알고리즘을 적용하여 X점에서 각각의 점 사이의 최단 경로를 구해준다. 최단 경로 리스트를 X_to_S라고 둔다.
   2. 이후, i점에서 다익스트라 알고리즘을 사용하여 X점까지의 거리를 구한 다음, X점에서 다시 i점으로 돌아가야 하므로 X_to_S[i]를 더해준 다음 정답을 갱신시켜 준다.
2. 다익스트라 알고리즘의 경우 거리가 가장 짧은 노드를 선택할 때 최소 히프를 사용해 주면 조금 더 빠르게 풀이를 할 수 있다.
3. 최종적으로 갱신된 정답을 출력한다.

---

소스 코드

---

import sys
import heapq

INT_MAX = int(10e9)

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

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

def dijkstra(X):
    heap = []
    time = [INT_MAX] * (N+1)
    time[X], time[0] = 0, 0
    heapq.heappush(heap, [0, X])

    while heap:
        curr_time, city = heapq.heappop(heap)
        if curr_time != time[city]:
            continue
        for e, t in graph[city]:
            if time[e] > t + curr_time:
                time[e] = t + curr_time
                heapq.heappush(heap, [time[e], e])

    return time

X_to_S = dijkstra(X)
answer = 0
for i in range(1, N+1):
    if i == X: continue
    answer = max(answer, dijkstra(i)[X] + X_to_S[i])

print(answer)