[백준] 1238번-(Python 파이썬) - Dijkstra

문제링크 : https://www.acmicpc.net/problem/1238

이번 문제는 이전에 풀었던 1916번 문제와는 다르게 왕복의 최단거리를 구하는 문제이다.
처음에 제대로 읽지 않고 갈때와 올때의 거리가 다르다는 점을 유의하지 않고 그냥 풀었다가 결국
다른 분의 코드를 한번 읽고 다시 풀었었다.

문제풀이
1. 출발지점에서 도착지점으로 가는 단방향 그래프와 왕복하는 그래프 만들기
2. 그래프에서 출발점에서 도착점으로 연결된 점을 이동해준다.
2-1. 출발점에서 도착점까지 최단거리로 이동하는데 드는 비용을 dp에 저장한다.
2-2. dp[이동할점]이 (현재 가중치 + 이동비용)보다 크면, 값을(현재가중치 + 이동비용)으로 바꿔준다.
3. 왕복시간이 가장 오래걸리는 학생을 구하라 했으니, 갈때와 올때의 합이 가장 큰 값을 출력해준다.

코드

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
n, m, x = map(int, input().split())
inf = sys.maxsize
graph = [[] for _ in range(n + 1)]
dp = [inf] * (n + 1)
graph_r = [[] for _ in range(n + 1)]
dp_r = [inf] * (n + 1)

def dijkstra(start, dp, graph):
    heap = []
    heappush(heap, [0, start])
    dp[start] = 0
    while heap:
        w, n = heappop(heap)
        if dp[n] < w:
            continue
        for n_n, wei in graph[n]:
            n_w = wei + w
            if n_w < dp[n_n]:
                dp[n_n] = n_w
                heappush(heap, [n_w, n_n])

for i in range(m):
    d, a, t = map(int, input().split())
    graph[d].append([a, t])
    graph_r[a].append([d, t])

dijkstra(x, dp, graph)
dijkstra(x, dp_r, graph_r)

max_ = 0
for i in range(1, n + 1):
    max_ = max(max_, dp[i] + dp_r[i])

print(max_)