C - ウサギとカメ arc025_3

Quiz

https://atcoder.jp/contests/arc025/tasks/arc025_3

Submit

https://atcoder.jp/contests/arc025/submissions/4186238

解き方と計算量

  • ゴールを固定する
    • ゴールから各ノードまでの距離をDijkstraで求める O( (N+M)logN )
    • 距離をソート O(NlogN)
    • (a) 亀の距離を固定したとき、ウサギの距離のしきい値も決まる
    • (b) upper_bound (二分探索)でウサギの取り得るノードの数も決まる
    • (a), (b) 合わせてO(NlogN)
  • ゴールも総当たりするので、全体ではO(N2 log N)
    • (N≒Mとした)

計算時間

  • 2500 x 2500 x log(2500) = 2 * 107
  • 実行時間制限 7秒
  • 私の提出では1秒ちょいかかるものもあった
  • 107はギリギリ通るようだ

テストケース1の場合 (0-index)

f:id:peroon:20190206232634j:plain