atcoder.jp
リハビリとして今日は最短経路問題の、アルゴリズムを実装するだけの簡単な典型問題を解きたかった。実装が正しいかチェックするためにオンラインジャッジが出来る問題を探したが、本当に実装するだけのよう問題を見るけるのは逆に難しく、少し変則的だが実装はほぼテンプレート通りのダイクストラ法という問題を見つけたので解いた。
問題なく解けたと言いたいところだったが、普通の最短距離の問題のように最短距離(この問題では最大のインデックス)よりも真に大きい(小さい)場合のみを除去すると枝刈りが十分ではなくTLEを受けてしまった。素直に確定した場合を記録して重複する探索を避けることでACになった。
atcoder.jp
