d_tutuz https://blog.hatena.ne.jp/d_tutuz/ 数学/競プロメモ https://tutuz.hateblo.jp/ 問題 https://atcoder.jp/contests/wupc2012-closed/tasks/wupc2012_5 考え方 頂点 から頂点 への最短経路(時間)を求める問題である。ただし頂点 の最短経路(時間)が か で割り切れる必要がある。頂点の情報だけでDijkstra法を適応してもうまくいかない。解を求めるために頂点に時間の情報も付与する必要がある。 サンプル の例でいうと、もともとは以下のグラフ。頂点の情報のみでノードが構築されている。 これに対して、頂点と時間の情報でノードを構築すると以下になる。 この拡張されたグラフ上で の倍数の場合と の倍数の場合でノードを構築した上… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftutuz.hateblo.jp%2Fentry%2F2019%2F01%2F26%2F140539" title="WUPC 2012：E - 会場への道 - 数学/競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/d/d_tutuz/20190126/20190126140005.png Hatena Blog https://hatena.blog 2019-01-26 14:05:39 rich https://tutuz.hateblo.jp/entry/2019/01/26/140539 1.0 100%