問題 https://atcoder.jp/contests/indeednow-finalb-open/tasks/indeednow_2015_finalb_d 考え方 よりなるべく多くの点 に訪問することが最適であることがわかる。つまり全頂点に訪問する。また最大値を最小値と読み替えると、グリッドグラフ上で最小全域木…

問題 https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_e 考え方 辺を拡張してダイクストラ法を適応させる拡張ダイクストラ法の問題である。ある時刻 において、文字列 の情報から次に上下左右に進むまでにかかる時間が分かる。まずこの各時…

問題 https://atcoder.jp/contests/wupc2012-closed/tasks/wupc2012_5 考え方 頂点 から頂点 への最短経路(時間)を求める問題である。ただし頂点 の最短経路(時間)が か で割り切れる必要がある。頂点の情報だけでDijkstra法を適応してもうまくいかない。解…

拡張Dijkstra法 グラフを拡張してDijkstra法を適応すること 「拡張ダイクストラ法」っていう言い方は、ダイクストラ法自体が拡張されている印象を受けるのでちょっとどうかと思う。「拡張グラフでのダイクストラ法」の方が適切では（まあこれを省略したのが…

牛ゲー 最短経路問題の双対問題を考えると線形計画問題になるということ 最短経路が定まっており、始点 からの頂点 への最短距離を とする。またコスト の から への辺を とすると と表すことができる。逆にこのような制約式で定式化される問題は最短経路問…