[白俊]504号-(Python Python)-Dijkstra

1638 ワード
白駿 dijkstra テキストリンク
質問リンク:https://www.acmicpc.net/problem/1504


この問題は方向性のない図形の中で2つの頂点を求めるときの最短距離の問題である.
v 1、v 2の2つの頂点を過ぎてn番の頂点に着くには、最初は必ずv 1、v 2を順番に通過しなければならないと思っていたが、問題を提起し、なぜ間違っているのか分からず、ずっと悩んでいた.
2つの頂点を通過しなければならない問題を解決すれば,すぐに多極値アルゴリズムを用いて解決できる.
リンクテキスト
Baek Jun(1916回)-「最小料金を求める」(ドエストラアルゴリズム)リンクで説明していますが、参考にすれば分かりやすいと思います.
import sys
from heapq import heappush, heappop

input = sys.stdin.readline
inf = sys.maxsize
n, e = map(int, input().split())
graph = [[] for _ in range(n + 1)]
dp_1 = [inf] * (n + 1)
dp_2 = [inf] * (n + 1)
dp_3 = [inf] * (n + 1)

def dijkstra(start, dp):
    heap = []
    heappush(heap, [0, start])
    dp[start] = 0
    while heap:
        w, n = heappop(heap)
        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 _ 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())
dijkstra(1, dp_1)
dijkstra(v1, dp_2)
dijkstra(v2, dp_3)

min_ = min(dp_1[v1] + dp_2[v2] + dp_3[n], dp_1[v2] + dp_2[n] + dp_3[v1])
if min_ >= inf:
    print(-1)
else:
    print(min_)
Python基礎辞書Dictionary
210319開発ログ(日付102)-返信アプリケーションの作成(新規返信アプリケーションの作成)