[Python]伯準1504特定の最短経路(Dijkstra)
9979 ワード
📌 質問する
方向性のないグラフを示した.勢俊は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
サンプル出力17
📌 に答える💬 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つを加えると最終的な最短経路となる.
Reference
この問題について([Python]伯準1504特定の最短経路(Dijkstra)), 我々は、より多くの情報をここで見つけました https://velog.io/@hygge/Python-백준-1504-특정한-최단-경로-Dijkstraテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol