猫でもわかるWeb開発・プログラミング猫でもわかるWeb開発・プログラミング本業エンジニアリングマネージャー。副業Webエンジニア。Web開発のヒントや、副業、日常生活のことを書きます。(お姫様の危機)どうも、yoshikyotoです。おかしかったので苦労してしまいました。そこから解決していこうと思います。そもそも冷凍施設についての行が消えてしまっています。テストケースでは、冷凍施設にについての行は、改行のみを含む1行が存在しています。しているとハマる可能性があります。解法スタートとゴールは冷凍施設がある街であるとみなします。ワーシャルフロイド法で任意の2つ街の最短距離を求めます。ワーシャルフロイドとはどういうアルゴリズムか、以下のようなグラフがあったとします。このグラフを以下のように更新するのがワーシャルフロイドです。任意の2点間のエッジにその2点間の最小距離が入るようにグラフを更新します。冷凍できない街は消す上のグラフに対して、下の図の青いノードが冷凍出来る街、赤いS,Gがスタート、ゴールだとすると、冷凍できない街とそこにくっついているエッジの情報は消してしまいます。今回の問題の場合、冷凍施設を持っている街同士の距離だけが重要となります。それ以外の街はただの道とみなしても問題ありません。ワーシャルフロイドを行ってから冷凍施設のない街を消すことで、冷凍施設の無い街はただの道であるとみなしています。ここで、距離がMより大きいエッジは削除してしまいます。これで、スタートからゴールまでがつながっていた場合は、血液を運ぶことができます。時間を求めるスタートからゴールまでの最短距離を求めます。いっちょワーシャルフロイドをしましょう。今回の場合は、たまたまひとつ前のグラフと全く同じになってしまいましたが、場合によっては違うグラフになることもあります。このグラフが意味していることは、「スタートからゴールまで血液を運ぶことが保証されていて、冷凍時間を除いたら3分間で到達できる」ということです。ここからどうやって時間を求めるのでしょうか。今回、M=2としていますので、スタートの時点でタイムリミットが2分です。運ぶ時間は3分なので、どこかで1分冷凍しなければなりません。よって運搬3分、冷凍1分で合計4分かかることになります。M=5であったとしたら、冷凍しなくて済むので運搬の3分のみとなります。説明が長くてわかりづらかったかもしれませんが、なんとなく分かっていただけたでしょうか?以下ソースコードとなります。今回はn=100なのでなんとか間に合います。入出力には自作クラスを使用しています。スポンサーをお願いしますブログを投稿したらX(twitter)でお知らせしています。