WUPC 2012：E - 会場への道
問題
https://atcoder.jp/contests/wupc2012-closed/tasks/wupc2012_5
考え方
頂点 から頂点
への最短経路(時間)を求める問題である。ただし頂点
の最短経路(時間)が
か
で割り切れる必要がある。頂点の情報だけでDijkstra法を適応してもうまくいかない。解を求めるために頂点に時間の情報も付与する必要がある。
サンプル の例でいうと、もともとは以下のグラフ。頂点の情報のみでノードが構築されている。
これに対して、頂点と時間の情報でノードを構築すると以下になる。
この拡張されたグラフ上で の倍数の場合と
の倍数の場合でノードを構築した上でDijkstra法を適応すれば解が求まる。それぞれ
のノードの最短距離(時間)が解になる。
Submission #4087140 - WUPC 2012
どこに着目して考察するべきだったか
解を求めるために必要な状態を頂点に持たせるという考え方が必要。
何がバグっていたか
得た知見(典型ポイント)
- 頂点を拡張してDijkstra法を適応
