久しぶりに拡張ダイクストラの問題 day2 にも拡張ダイクストラが出ていたりする。 ダイクストラといっても、距離は一切出てこなくて、休憩回数の最小値を求める問題。 heap で (累計の休憩回数、前の隙間、今いる頂点）を保管して、今いる頂点から次の頂点に…

拡張ダイクストラで解く。総時間、頂点に加えて今持っている銀貨の数を追加して heap に入れる。時間を増やす要因が通過時間と通貨を交換する時間の二つ（疲れているのでダジャレみたいになっている）あるので、交換するか、移動するかで分けて考える。移動…

拡張ダイクストラの簡単な問題ということで、まず解いてみました。通常のダイクストラと何が違うかというと、例えば、頂点が3つなら最小距離を保存するリスト d も d = [float("inf")] * 3 とかで十分でしたが、今回の問題のように、総距離が４の倍数になる…

ダイクストラ法の問題 この問題は道路を片方向にしか通れないので、１からｋまでの最短路とｋから1までの最短路は別に求める必要がある。 import sys input = sys.stdin.readline n,m,t = map(int,input().split()) a = list(map(int,input().split())) a = …