Skip to main content
本文に 221 文字追加
ソース リンク
user18851
  • 1,238
  • 8
  • 6

問題の解説サイトを読みましたか?
https://www.ioi-jp.org/joi/2016/2017-yo/2017-yo-t6/review/2017-yo-t6-review.html

質問まず、質問者のプログラムは ダイクストラ法になっていません。
while 分で取り出した1つの部屋について すべての訪問可能な部屋の情報を調べて計算し
少しでも効率がいい経路を queue に入れていますが、再帰的にすべてのルートを計算しているのとそれほど変わりがありません。

まず、ダイクストラ法を使って計算するロジックを書く練習をしてください。
ダイクストラ法では、次の部屋へ到達する最短距離は、前の部屋への最短距離を保持した配列から
計算することで無駄な計算を行わないというアルゴリズムです。

問題の解説サイトを読みましたか?
https://www.ioi-jp.org/joi/2016/2017-yo/2017-yo-t6/review/2017-yo-t6-review.html

質問者のプログラムは ダイクストラ法になっていません。
while

問題の解説サイトを読みましたか?
https://www.ioi-jp.org/joi/2016/2017-yo/2017-yo-t6/review/2017-yo-t6-review.html

まず、質問者のプログラムは ダイクストラ法になっていません。
while 分で取り出した1つの部屋について すべての訪問可能な部屋の情報を調べて計算し
少しでも効率がいい経路を queue に入れていますが、再帰的にすべてのルートを計算しているのとそれほど変わりがありません。

まず、ダイクストラ法を使って計算するロジックを書く練習をしてください。
ダイクストラ法では、次の部屋へ到達する最短距離は、前の部屋への最短距離を保持した配列から
計算することで無駄な計算を行わないというアルゴリズムです。

ソース リンク
user18851
  • 1,238
  • 8
  • 6

問題の解説サイトを読みましたか?
https://www.ioi-jp.org/joi/2016/2017-yo/2017-yo-t6/review/2017-yo-t6-review.html

質問者のプログラムは ダイクストラ法になっていません。
while