2017-05-14 競技プログラミングにおける最短経路問題まとめ [ダイクストラ, ベルマンフォード, ワーシャルフロイド] 競技プログラミング 最短経路を求めるには ダイクストラ【単一始点最短経路】 参考1 参考2 応用して各頂点のある値の最大値を求めるダイクストラもある ベルマンフォード（Bellman-Ford）【単一始点最短経路】 ダイクストラと違い、負のコストを含む辺があっても正しく動作する 負のサイクルがあると止まらないため、負のサイクル検出ができる 参考 最長距離を求めるようにも書け、その場合は正のサイクル検出ができる(ABC061D) 6Nくらい回せばいいらしい（要出典） 幅優先探索 BFS【単一始点最短経路】 辺のコストが1ならばBFSで十分 ワーシャルフロイド【全頂点間最短経路】 参考1 参考2 O(N^3) 問題 ダイクストラ ARC090 Avoiding Collision 解説 JOI 象使い 問題 解説 AOJ 認証レベル 解説 （ちょっと変えたダイクストラ） RUPC2018 Day2 Light 解説 KOJ No.73 観光計画 解説（最大値ダイクストラ） AC 迷路 解説 CF372 Complete The Graph AOJ Gridgedge 解説 AOJ スギ (Demon's Cedar) 解説 yukicoder No.788 トラックの移動 解説 AOJ こたつがめを燃やさないで 解説 yukicoder No.807 umg tours 解説 ベルマンフォード ABC061 D. Score Attack AOJ Set-constructing Witch (舞台装置の魔女) 解説 AOJ The Most Powerful Spell 解説1 解説2 東京工業大学プログラミングコンテスト2015 N. 何かグラフの問題 解説 BFS 競技プログラミングにおける幅優先探索問題まとめ [BFS, 後退解析] - はまやんはまやんはまやん ワーシャルフロイド ABC073 joisino's travel 解説 ABC079 Wall 解法 CSA70 Min Distances RUPC2017 Day3 AA Graph 解説 RUPC2017 Day3 最短距離を伸ばすえびちゃん (Ebi-chan Lengthens Shortest Paths) 解説