[Python]伯準1504特定の最短経路(Dijkstra)

📌 質問する
方向性のないグラフを示した.勢俊は1番頂点からN番頂点までの最短距離を移動したい.また,ポテンシャル俊は,任意に与えられた2つの頂点が通過しなければならないという2つの条件を満たす移動の特定の最短経路を求めたい.
勢俊は一度の頂点だけでなく、一度の幹線も移動できる.しかし最短経路に移動しなければならないという事実に注意しなければならない.1番の頂点からN番の頂点に移動する場合は、2つの頂点を指定しながら最短パスに移動するプログラムを作成します.
入力
第1行は、頂点の個数Nと、幹線の個数Eとを与える.(2≦N≦800,0≦E≦200000)2行目からE行まで3つの整数a,b,cがあり、a番頂点からb番頂点まで双方向の長さがあり、その距離はcである.(1≦c≦1000)次の行は、通過しなければならない2つの異なる頂点番号v 1およびv 2を与える.(v1 ≠ v2, v1 ≠ N, v2 ≠ 1)
しゅつりょく
2つの頂点を通過する最短パスの長さを1行目に出力します.このようなパスがない場合は、-1が出力されます.
入力例1

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

サンプル出力1

7

📌 に答える
💬 Code

import sys, heapq
input = sys.stdin.readline
INF = float('inf')


def dijkstra(start):
    distance = [INF for _ in range(n+1)]
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if dist > distance[now]:
            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]))

    return distance


n, e = map(int, input().split())
graph = [[] for _ in range(n+1)]

for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

v1, v2 = map(int, input().split())

# 1 - v1 - v2 - n
dist1 = dijkstra(1)[v1] + dijkstra(v1)[v2] + dijkstra(v2)[n]

# 1 - v2 - v1 - n
dist2 = dijkstra(1)[v2] + dijkstra(v2)[v1] + dijkstra(v1)[n]

ans = min(dist1, dist2)
print(ans if ans != INF else -1)

💡 Solution
すべてのノードの最短パスを求める必要がある問題はfloodで解くのは簡単ですが、この問題のようにノードの数が500個を超えるとfloodを使用するとタイムアウトします.
したがって、1つのノードから他のすべてのノードへの最短パスを求めるために、複数のカーブを複数回実行する必要があります.
たとえば、1からv 1、v 2からnまでの最短パスが必要です.
「マルチタスク1」を実行した後、1からv 1へのパスを求める.
複数のExpstra v 1を実行した後、v 1からv 2へのパスを求める.
複数のstrav 2を実行した後,v 2からnへの経路を求め,さらに3つを加えると最終的な最短経路となる.