競技プログラミング用 知識集積所
ABC422F - Eat and Ride
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
一見Dijkstra法※の問題に見える。
しかし、過去の経路次第でコストが変わるので、うまくいかない。
燃料5の体重4で来た後に、燃料6の体重3で来る場合があり、同じ頂点を複数回処理する必要があるかもしれないからである。
しかし、過去の経路次第でコストが変わるので、うまくいかない。
燃料5の体重4で来た後に、燃料6の体重3で来る場合があり、同じ頂点を複数回処理する必要があるかもしれないからである。
- 絶対にn回移動する
- スタート地点でコスト0で1回分足踏みしてもよいとする
というように条件を変えても、答えは同じものになるから。
この場合、1つ目の到達地点の食事の重さは（足踏みでない限り）必ずn回分加算されることになる。
同じく、2つ目の到達地点の食事の重さは（足踏みでない限り）n-1回分加算される。
よって、「その食事分はゴールするときまでの分を一気に足してしまう」という方法で、1回ごとに全頂点への燃料の最小値を求める動的計画法を動かすことができる。
スタート地点での足踏みは、1回の移動を計算するごとにスタート地点の値をリセットすることで対応できる。
同じく、2つ目の到達地点の食事の重さは（足踏みでない限り）n-1回分加算される。
よって、「その食事分はゴールするときまでの分を一気に足してしまう」という方法で、1回ごとに全頂点への燃料の最小値を求める動的計画法を動かすことができる。
スタート地点での足踏みは、1回の移動を計算するごとにスタート地点の値をリセットすることで対応できる。
解答例
注意点
答えがint型に入りきらない場合がある
明らかに21億を超えることがある。
long long型を用いること。
long long型を用いること。
