htkb-proconの日記

初心者がPythonで問題解いた記録

ABC012-D 最短経路問題

D - バスと避けられない運命

最短経路問題の練習をいくつかこなしていたら、ダイクストラを真っ当に実装したはずなのにめっちゃTLEが出るこの問題に遭遇。おかしいと思って解説を読むと、

•注意点
– 遅い言語では通りません!
Perl, Ruby, Pythonなど
• 計算量が一定以上重い問題だと、LL系の言語では、通すことが 出来ません。
– 言語の選択もコンテストのうちです!

お?やんのか?ってことで色々いじって通した。

Submission #1289371 - AtCoder Beginner Contest 012 | AtCoder

  • やること

    • 各頂点ごとに最短経路を出してその最大を出力する
  • やったこと

    • 基本ダイクストラ
    • 計算した最短距離はメモっておき再利用する(AからBの最短距離を出したら、BからAへの最短距離に使い回す)
      • memo[n]がそれ
      • メモから読んだ頂点は訪問済みにし初期キューにもあらかじめ入れとく
    • 再帰的に隣接頂点を呼んで、隣接頂点の計算が終わったら子から親への枝を切る(これ怪しい……)
      • solve(child)後にedges[child].remove(i)で子→親方向の枝のみ切ってる
      • 逆方向(親→子)への枝を切るとWA出るので正当性は不明
    • 基本的な枝刈り
      • コストが低い頂点へは最初から行かない
      • メモしたコストを写した頂点には行かない(最短確定してるので)
      • 全訪問済みになったらwhileを抜ける

優先度付きキューを使ったダイクストラO((E+V)log V)でこれを各頂点に行うので、制約:V≦300,E≦44850から計算量はおよそ108くらい?基本的にpythonでは107の時点で無理ゲーな感じだけど、色々パズル感覚でこねくり回して通ってうれしい。