다익스트라, 그래프 - 1238번: 파티

1) 역방향 그래프로 i -> X 최단거리 구하기(to_x)

: 모든 마을에서 X까지의 최단거리를 구할 때 각 마을에서 n번 실행하는 것은 비효율적이므로, 역방향 그래프에서 X에서 출발하여 모든 노드로 가는 최단거리를 구하면 모든 i -> X 거리를 한번에 계산할 수 있음

2) 정방향 그래프로 X -> i 최단거리 구하기(from_x)

3) 모든 i에 대해 to_x[i] + from_x[i] 계산 후 최댓값 출력하기

import sys
from collections import defaultdict
import heapq

data = sys.stdin.readlines()

line = list(map(int, data[0].split()))
n, m, x = line[0], line[1], line[2]

dict = defaultdict(list)
dict_rev = defaultdict(list)

for i in range(1, m + 1):
    data[i] = list(map(int, data[i].split()))
    dict[data[i][0]].append([data[i][2], data[i][1]]) # 정방향 그래프(cost 먼저)
    dict_rev[data[i][1]].append([data[i][2], data[i][0]]) # 역방향 그래프(cost 먼저)


def dijkstra(graph, start, n):
    # 최대 거리로 전체 초기화, x에서 시작하여 n으로 가는 경로이므로 1차원 리스트로 선언하기
    dist = [float('inf')] * (n + 1)
    dist[start] = 0 # x에서 x로 가는 거리는 0

    heap = [(0, start)]
    
    
    while heap:
        cost, now = heapq.heappop(heap)

        if dist[now] < cost: # 현재 경로보다 이전에 저장해둔 경로가 더 최단경로라면 패스
            continue
        else:
            # 현재 노드에서 갈 수 있는 모든 노드에 대해
            for elem in graph[now]:
                next = elem[1]
                next_cost = elem[0]
                # 새 비용 = 현재 비용 + 다음 노드로 가는 비용
                new_cost = cost + next_cost
                if new_cost < dist[next]: # 새 비용이 다음 노드의 기존 경로보다 더 최단경로(low cost)라면
                    dist[next] = new_cost # 비용 갱신
                    heapq.heappush(heap, (new_cost, next)) # cost, 현재 노드
    return dist

to_x = dijkstra(dict_rev, x, n) # i -> X 최단거리: 역방향 그래프에서 X -> i로 가는 최단경로로 구하기

from_x = dijkstra(dict, x, n) # X -> i 최단거리: 정방향 그래프에서 X -> i로 가는 최단경로로 구하기


max_time = -1

for i in range(1, n + 1):
    # X로 갔다가 다시 집으로 돌아오는 총 시간을 누적하여 최댓값 구하기
    time_sum = to_x[i] + from_x[i]

    max_time = max(max_time, time_sum)

print(max_time)