拡張ダイクストラ前回の問題で、拡張ダイクストラを使った。キューにぶち込む値の組を変えていくってことかな？普通のダイクストラの場合は、プライオリティキューに現時点での距離を先頭に、頂点をその次にしたリスト(or タプル)を入れる。これを拡張させた…

qiita.com 続き。 atcoder.jp dijkstraでどうやってやんだよ...って思って、dijkstraの解答を探した。 ferin-tech.hatenablog.com 拡張ダイクストラとは？？？？？？？？？？？？？？？？？？？？？ 明日一通り調べよう... H, W = map(int, input().split())…

昨日の続きです。昨日は、考えでは、ダメなことがわかったので、解答を見た。考えは、だいぶ似ていた。ただし、最短経路上の単位獲得金額がでかい都市を探す必要がなかった。すべての都市を往復することで、経路上の単位獲得金額がでかい都市を特定すること…

qiita.com 続き。 atcoder.jp 考えたこと 1 に戻ってくる最短経路をTから引いて、経路内で最も単位あたりの獲得金額が高い頂点を探して、そこで最大限いたことにするというものを実装してみた。結果的にダメだった。8割くらいACしたけど、残り2割がダメだっ…

qiita.com 続きです。 atcoder.jp これはすげー簡単だった。まぁ100点問題だしね。 コピペで瞬殺！！！ import queue push = queue.heappush pop = queue.heappop INF = 10**16 def dijkstra(s, G, d): q = [] d[s] = 0 push(q, (0, s)) while q: cost, v = …

qiita.com 続きです。 atcoder.jp ダイクストラな問題みたい。普通にわからんかったが。 editorial.pdfを見て実装してみる。 最後の出力が になってここがボトルネックになってTLEになっている。editorialにもここの処理書いてないやん。適当に検索したら、…

こんにちは、えぬわいです(普通) ダイクストラ法の復習です。 import queue push = queue.heappush pop = queue.heappop INF = 10000 from collections import defaultdict G = defaultdict(list) N, M, S, GOAL = map(int, input().split()) V = N d = [] f…

自分の中で、けものみちが熱いです。 qiita.com 続き。 atcoder.jp 難しいなぁと思いながら、解説は理解できたが、実装がわかんなかったので、実装例を見てみた。 kmjp.hatenablog.jp お世話になってる kmjp さん！！！かっけー pythonで書き直し。 from sys…

前回の記事で、解説みると、奇数長の閉路を探索する必要があることがわかった。 閉路の検出ってどうやるんだっけなぁって思って調べた。 inzkyk.github.io わかりやすい。擬似コードも載ってる。確認する。 from collections import defaultdict G = default…

qiita.com 続きをやっている。 atcoder.jp 普通にわかんなかったが？(半ギレ) 解答見る。 考察で、逆順に辿ると、上書きする機能がなくなる←天才か？ 始点と最初の色で全探索。それプラス、奇数サイクルのことを考えるものらしい。 辺彩色のコードわからんと…