문제

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

Input)
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
Output)
10

point

Priority Queue(heap) 이용

• 매번 이동 할 수 있는 노드 중 거리가 최소인 노드로 이동하므로, 이동 가능 한 노드를 pq에 담아준다.(거리와 함께)

거리를 최대값(무한대)로 초기화

• 최소거리를 구해야 하기 때문에 초기값을 가질 수 있는 최대값으로 초기화 한다.

큐에 넣은 노드를 이후에 다시 넣을 수도 있다.

• 방문한 순서가 최소거리에 영향을 주지 않는다.
• 그러므로 큐에 넣을 때 방문 여부를 체크하면 안된다.
  : 나중에 넣는 경로가 거리가 더 짧을 수도 있으므로
• 큐에서 꺼낼 때 경로를 비교해서, 이번에 꺼낸 거리가 기존에 저장된 거리보다 더 길다면 아무 처리도 하지 않고(인접 노드를 큐에 넣지 않고) 넘어간다. (continue)

전체코드

import heapq

n, m, x = [int(x) for x in input().split()]

road = [[] for _ in range(n + 1)]
road_time = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(m):
    a, b, c = [int(x) for x in input().split()]
    road[a].append(b)
    road_time[a][b] = c

def dijk(s):
  global road, road_time, x
  time = [100*n] * (n + 1)
  pq = []
  heapq.heappush(pq, (0, s))
  time[s] = 0
  while(pq):
    cur_t, cur_n = heapq.heappop(pq)
    if cur_t > time[cur_n]:
      continue
    for a in road[cur_n]:
      next_t = cur_t + road_time[cur_n][a]
      if next_t < time[a]:
        time[a] = next_t
        heapq.heappush(pq, (next_t, a))
  return time

time = dijk(x)
for i in range(1,n+1):
  if i != x:
    time[i] += dijk(i)[x]

print(max(time[1:]))