読者です 読者をやめる 読者になる 読者になる

研究や趣味やらあれこれ

日々のあれこれをあれ

yukicoder No.1 道のショートカット

だーいぶ遅くなったけどとりあえず更新

 

最近yukicoderなるとこで競技プログラミングの練習を始めた

 

言語はJavaです。速さなんて知らない

 

多分星3とか4は飛ばすことあると思うけど、1から順にGitにアップしていこうと思う

 

yukicoder/src at master · gazinao/yukicoder · GitHub

 

とりあえずNo1。

 

N個の街と所持金Cがあって、ある街からある街へつなぐ道がV個ある。道にはそれぞれかかるお金と時間が与えられていてこの時、街1から街Nへ行くとき所持金内で行ける経路で最速のものを選んだ場合にかかる時間を求めよ、という問題

 

街番号が大きいものから小さいものへの経路は考えなくて良いとある

 

ので、速さだけ求めるならダイクストラとかいうDPっぽいもので、各街まで行くのに最速の経路を街番号が小さいものから順に更新していけば良い

 

プログラム的には、n番目の街に到達する最速の時間をt[n-1]とし、それぞれを更新していけば最終的にt[N-1]が答えになる

 

しかし今回はコストも考慮しなければならない

 

はじめに思い浮かんだ方法は、最小時間でダイクストラしていってコストオーバーした時点で道を戻り次にコストの低い道を選ぶ、というものだった

 

でもこれだと次にコストの低いものでゴールできても、すべての道で最速とは限らないのでボツ

 

てことで、思いついたのがダイクストラでできるようにコストの概念を消す方法

 

各街をC+1個にコピーして、所持残高で入れる街を制限してダイクストラ。最後にN番目の街すべての中から一番早いものが答えとなる

 

プログラム的には、t[N]をt[N][C+1]に拡張しダイクストラ。所持金が足りなくなる、つまり更新先の配列のインデックスがマイナスになる場合更新しない

 

でACいただけました

 

実行時間:211ms コード長:2162Byte(コメントって含まれるのかな?)

 

解説もこんな感じだったと思うし解けてよかった(小並感)