• このエントリーをはてなブックマークに追加

スポンサードリンク

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14091&rd=16625

n個の街がある。二つの街を移動するには、dist[i][j]時間かかる.

また、k magic pointが与えられる。 magic pointをつかうと移動時間を半分にすることができる.

街0から1への最小の移動時間を求めよ.

方針

ダイクストラ法をつかうのだと思った.

以下のリンクを参考に実装してみた.

ポイントは、magic pointをk回つかうことで、最小の移動時間が変動すること. 0から1へk回 magic pointをつかった結果を記憶しておいて、 最後に、その結果のなかでの最小値を求める.

で、いいのかな?? よくわからず、もう5時間くらい悩んでいるのだけれども。。。

回答