No Caffeine, No Life

プログラミング(主にPython)

ABC 073 D - joisino's travel:ダイクストラ法、ワーシャルフロイド法、組み合わせ(itertools)

問題:

D: joisino's travel - AtCoder Beginner Contest 073 | AtCoder

解説:

  • 訪れる町が{\displaystyle R (2 \leq R \leq min(8, N) ) }個と少ない。そこで、全通りの順列を全探索。
  • 各点から各点への最短距離はダイクストラ法で求める。負の距離が無いし。

と、コンテスト中は考えた。これでうまくいくのだけれど、2個だけTLEしてしまい、そこをなんとかするのに手間取ってしまった。気づいてしまえば、なんてことはないのだけれど…勿体ない…。

 後ほどAtcoderが提供する解説を見て、全点間での最短距離を求めるならワーシャルフロイド法を用いればよい(今回は頂点数も少ないので)、と書かれている。確かに。確かに、ではあるのだけれど、pythonでは結構ぎりぎり通るくらいのもので、やはりスピードとしては上記の方法の方がよかった。