https://www.acmicpc.net/problem/1238
時間1秒、メモリ128 MB
input :

N M X (1 ≤ X <= N ≤ 1,000)(1 ≤ M ≤ 10,000)

u v c (1 <= c <= 100)

output :

出力

条件:

起点と一つの都市Aから別の都市Bへの道路は最大1本である.

これらの学生はもともと怠け者で,最短時間で行き来したいと思っている.

これらの道路は一方通行である

問題をよく読んでいないことだけを議論した.そして、すべての村を計算するよりも良い方法を見つけなければなりません.

次の解

行き交い、

が要求する目的地X

Xを計算するには、Xから来たのです.
複数のカーブを使用して最短距離を求める

Xから他の村に戻るすべての状況を元の方向に計算することができます.

幹線の方向を反転させると、その村->Xのすべての状況を計算することができる.もちろん,Xから他の村までの場合,計算した値は同じ結果を得た.
だから2番はすべてExpstraをして、相応の配列を合わせて、それから最低価格を探せばいいです.

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:]))