BOJ 1162道路舗装

https://www.acmicpc.net/problem/1162
2秒、128 MBメモリ
input :

N M K(1 ≤ N ≤ 200,000)(1 ≤ M ≤ 50,000)(1 ≤ K ≤ 20)

都市時間(双方向道路、1<=時間<=10000)

output :

K以下の道路で、

で出力される最小時間
条件:

舗装だけ

包装ができていれば、道路を通るのにかかる時間は0です.

1番からN番までずっと行けるデータだけをあげます.

一番重要な部分はどの道を敷くかです.

すべての場合の数値の表示
もちろん爆発します.50000個の中から20個の組み合わせの睡眠を選びます...想像したくない.

きろく
結果はすべて記録しなければならない.前に敷いた道路の個数で今の道路を敷くかどうかを考えます.

考える過程は今度はこうしましょう.
特定の道を行くには、どんな方法がありますか?そのまま歩いたり、相応の道を敷いたりします.
これはどうやって記録しますか?それをqに入れるときは、今の方法で何回包装できるか考えてみましょう.
この部分を考えたら残りはDaestraでいいと思います.
基本コードに示すように、while文の下に条件文を追加し、保存した最短距離よりも現在のコストが大きい場合にのみ確認します.
この部分はvisit部分に代わっています.
注意する.
1.双方向
2.dpを初期化するすべての開始ノード
3.距離を更新してqに追加

import sys
from heapq import heappop, heappush

n, m, k = map(int, sys.stdin.readline().split())
graph, distance = [[] for _ in range(n + 1)], [[float('inf')] * (k + 1) for _ in range(n + 1)]

for i in range(k + 1):
    distance[1][i] = 0

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a].append((c, b))
    graph[b].append((c, a))

q = []
heappush(q, (0, k, 1))
while q:
    cost, cnt, node = heappop(q)

    if cost > distance[node][cnt]:
        continue

    for next_cost, next_node in graph[node]:
        if cnt >= 1 and cost < distance[next_node][cnt - 1]:
            distance[next_node][cnt - 1] = cost
            heappush(q, (cost, cnt - 1, next_node))

        if cost + next_cost < distance[next_node][cnt]:
            distance[next_node][cnt] = min(distance[next_node][cnt], cost + next_cost)
            heappush(q, (cost + next_cost, cnt, next_node))

print(min(distance[n]))