BOJ 1504特定の最短パス

8882 ワード
2021.02.10 テキストリンク
https://www.acmicpc.net/problem/1504
1秒、256 MBメモリ
input :
  • N E(2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000)
  • a,b,cが与えられ、a番頂点からb番頂点まで双方向路が存在し、その距離はcである.(1 ≤ c ≤ 1,000)
  • の2つの異なる頂点番号v 1およびv 2が与えられる.(v1 ≠ v2, v1 ≠ N, v2 ≠ 1)
    • output :
    出力
  • 最短パスの長さ.このパスがない場合、出力-1
    • 条件:
  • 1番頂点からN番頂点に移動するとき、与えられた2つの頂点を介して最短経路に移動するプログラム
    • .
    1番からNに移動して2時を通過する方法は?
    1 - v1 - v2 - n
    1 - v2 - v1 - n
    二つのケースしかありません.
    1から最短経路を探して
    v 1の中の最短経路を求め,v 2の中のすべての最短経路を求める.
    パスの距離を比較して、出力がもっと短いです.
    import sys
import heapq

n, e = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n + 1)]
for i in range(e):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
v1, v2 = map(int, sys.stdin.readline().split())

def dijkstra(start):
    ret = [999999] * (n + 1)
    ret[start] = 0
    q = []
    heapq.heappush(q, (0, start))

    while q:
        cost, now = heapq.heappop(q)

        if cost > ret[now]:
            continue

        for next_node, next_cost in graph[now]:

            total_cost = next_cost + cost

            if ret[next_node] > total_cost:
                ret[next_node] = total_cost
                heapq.heappush(q, (total_cost, next_node))
    return ret

one = dijkstra(1)
list_v1 = dijkstra(v1)
list_v2 = dijkstra(v2)
ret = min(one[v1] + list_v1[v2] + list_v2[n], one[v2] + list_v2[v1] + list_v1[n])
if ret < 999999:
    print(ret)
else:
    print(-1)
    今日はもう一回heap
    今日のホットスポットレンダリング
    [BOJ] - 2742