https://www.acmicpc.net/problem/1238
시간 1초, 메모리 128MB

input :

• N M X (1 ≤ X <= N ≤ 1,000)(1 ≤ M ≤ 10,000)
• u v c (1 <= c <= 100)

output :

• 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력

조건 :

• 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개

• 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

• 이 도로들은 단방향

문제를 제대로 안 읽어 가는 경우만 따졌다. 그것도 그렇고 모든 마을에서 X로 가는 것을 계산하는 것보다 더 나은 방도를 찾아야 했다.

다음 풀이

1. 오고 가는데에
2. 요구하는 도착지 X

X로 가고, X에서 오는 것을 따져야 한다.
다익스트라를 사용하여 최단 거리를 구하라는 의미

원래의 방향으로는 X에서 다른 마을로 돌아가는 모든 경우를 계산할 수 있다.

간선의 방향을 뒤집은 경우, 해당 마을 -> X로 가는 모든 경우를 계산할 수 있다. 물론 X에서 다른 마을로 가는 경우의 값을 계산한 것이 동일한 결과를 가진다.

그래서 2번 다익스트라를 수행하고 해당하는 배열을 합한 후에 최댓값을 찾으면 된다.

import sys
from heapq import heappop, heappush

def dijkstra(graph):
    q = []
    heappush(q, (0, x))

    dist = [float("inf")] * (n + 1)
    dist[x] = 0

    while q:
        cost, node = heappop(q)

        if cost > dist[node]:
            continue

        for next_cost, next_node in graph[node]:
            temp = next_cost + cost
            if dist[next_node] > temp:
                dist[next_node] = temp
                heappush(q, (temp, next_node))
    return dist

n, m, x = map(int, sys.stdin.readline().split())
original, reverse = [[] for _ in range(n + 1)], [[] for _ in range(n + 1)]

for _ in range(m):
    u, v, c = map(int, sys.stdin.readline().split())
    original[u].append((c, v))
    reverse[v].append((c, u))

ori_dist = dijkstra(original)
rev_dist = dijkstra(reverse)
for i in range(n + 1):
    ori_dist[i] += rev_dist[i]

print(max(ori_dist[1:]))