1238 - 최단경로(다익스트라)

단방향 그래프 문제들은 보통

노드1 - 노드2로 가는 간선과 노드2 - 노드1 간선이 무조건 같은 간선인 줄 알았다.
노드간 도로가 2개 이상 존재할 수도 있다는 것을 인지 (특정 노드까지 가는 거리와 특정 노드에서 출발 노드까지 다시 오는 거리가 다를 수도 있음)

문제는 노드 간 도로(간선)을 여러개 주고 모든 노드에서 특정 노드까지 갔다 오는 거리를 계산하는 것이다.

특정 노드에서 모든 노드까지의 최단거리는 보통의 다익스트라로 구할 수 있지만 (모든 노드에서 특정 노드까지 도착 후에 다시 돌아가는 거리) 모든 노드에서 특정 노드까지 가는 거리는 모든 노드에서 다익스트라를 한 다음 모든 노드의 최단거리 리스트를 확인하여 특정 노드까지의 최단 거리를 각각 다 구해줘야 한다.

하지만 처음 입력 받는 간선을 거꾸로 저장한 그래프를 추가로 만든다면 (1->2 비용3 이라면 2->1 비용3 이런식으로) 그 그래프로 특정 노드에서 다익스트라를 실행했을 때 모든 노드에서 출발하여 특정 노드까지 걸리는 최단 경로도 구할 수 있다.
https://kangmin1012.tistory.com/8

정리하자면,
특정 노드에서 다익스트라를 두번 실행하는데 첫번째는 정방향, 원래 그래프대로 하고
두번째는 그래프의 간선 정보가 거꾸로 되있는 그래프에서 실행하여 두 값을 더하면 각 노드에서 특정 노드까지 갔다 오는 거리를 구할 수 있다.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n,m,x = map(int, input().split())
graph = [[]for i in range(n + 1)]
graph_reverse = [[]for i in range(n + 1)]

for _ in range(m):
  first, second, t = map(int, input().split())
  graph[first].append((second,t))
  graph_reverse[second].append((first,t))
  
distance_VtoP = [INF] * (n+1)
distance_PtoV = [INF] * (n+1)

def dijkstra(start, graph, distance):
  q = []
  heapq.heappush(q, (0,start))
  distance[start] = 0

  while q:
    dist, now = heapq.heappop(q)
    if distance[now] < dist:
      continue
    for i in graph[now]:
      cost = dist + i[1]
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost,i[0]))

dijkstra(x, graph, distance_VtoP)
dijkstra(x, graph_reverse, distance_PtoV)

result = []
for i in range(1, n+1):
  result.append(distance_VtoP[i] + distance_PtoV[i])

print(max(result))