2008JOI予選6 船旅解説

解説

典型的な最短経路問題です。最短経路問題については、この記事で包括的に扱っています。

この問題は、ダイクストラ法を用いて $O(k^2 \log n)$ で解くことができます。ただし、ほとんどのテストケースでは最悪計算量がかかることがないため、余裕をもって正解することができます。

また、ワーシャル・フロイド法を用いれば $O(kn^3)$ で解くこともできます。一見正解は難しそうですが、実はこの方法でも正解が取れます。

ところで、この問題の実行時間制限は10秒です。このように、実行時間制限が標準より長いときは、解法の計算量オーダーが予測できることがあります。これは解法にたどり着くまでの手助けとなる場合も多くあるので、特に情報オリンピックでは実行時間制限を気にかけておくようにしましょう。

また、ダイクストラ法などの最短経路問題は非常によく出題されます。最短経路問題に帰着できる問題が予選のボーダーとなることは多いので、この機会に身につけましょう。上にリンクを挙げたkaageの記事をぜひ使ってください。