質問: 2: print('POSSIBLE') else: print('IMPOSSIBLE') ```
回答: 上記の回答では ダイクストラ法を使って 到達目的の島の最短距離を求めて 最終的に その距離が 2 であれば OK というロジックになっていると思います。 Python が詳しくないので C# で 上記コードと同じアルゴリズムを実行した結果 2つの問題で `TLE` が発生する事を確認しました。 何パターンかアルゴリズムの改善を試してみましたが、 ``` for ship in ships ``` とする部分が 船の数が多い時に ループの回数が多くて遅くなっているようです。 島を特定して その島から 次の島を判定するために 200,000 も 定期便があった場合に 処理速度が遅くなっているのだと思います。 最初の 読み込み時に 島から 定期便1本で行ける 次の島の情報を リストに保管しておくことで 無駄なループが減り `TLE` にはならずに すべて 0.5 秒以内に回答できるようになりました。 また、 ちょっと気になったのですが、 定期便は 双方向なので from -> to と 逆の to -> from の経路も考慮しておかないと 正しい答えにはならない気がします。 ダイクストラ法で 解くのもありかもしれませんが、 『定期便を 2 つ使うことで、島 N に行けるか調べたいと思っています。』 というように書かれているので、 わざわざすべての経路の最短経路を求める ダイクストラ法を使うのは時間の無駄な気がします。 出発の島 -> 中間の島 → 到達の島 となる 中間の島 を探すのが目的なので 出発の島 から の定期便のある 中間の島 の集合 A 到達の島 に行くことができる 定期便のある 中間の島の集合 B を調べて A と B を両方満たす島を見つける。 という単純な 回答が一番ふさわしい気がします。