ABC232 G - Modulo Shortest Path - かんプリンの学習記録

問題はこちら

問題概要
解説
- 例
提出プログラム
感想

問題概要

${N}$ 頂点のグラフがあり，頂点 ${i}$ から頂点 ${j}$ に重み ${A_i+B_j\bmod{M}}$ の有向辺が張られている．頂点 ${1}$ から頂点 ${N}$ までの最短距離を求めよ．

${2\leq N\leq 2×10^5\\ 2\leq M\leq 10^9\\ 0\leq A_i,B_i < M}$

解説

${A_i+B_j < 2M}$ であるから ${A_i+B_j\bmod{M}}$ は

${A_i+B_j < M}$ なら ${A_i+B_j}$
${A_i+B_j \geq M}$ なら ${A_i+B_j-M}$

となります．

頂点を ${B}$ でソートすると，各 ${i}$ について ${A_i+B_j < M}$ となる ${j}$ や ${A_i+B_j \geq M}$ となる ${j}$ は連続します．したがって，頂点を ${B}$ でソートし(つまり ${B_i\leq B_{i+1}}$ となるように頂点番号を振りなおし)以下のようなグラフを考えればよいです．

頂点は ${X_i,Y_i(1\leq i\leq N)}$ の ${2N}$ 個．
${X_i}$ から ${Y_1}$ に重み ${A_i+B_1}$ の有向辺を張る( ${1\leq i\leq N}$ )．
${Y_i}$ から ${X_i}$ に重み ${0}$ の有向辺を張る( ${1\leq i\leq N}$ )．
${Y_i}$ から ${Y_{i+1}}$ に重み ${B_{i+1}-B_i}$ の有向辺を張る( ${1\leq i\leq N-1}$ )．
${A_i+B_j\geq M}$ となる最小の ${j}$ に対し， ${X_i}$ から ${Y_{j}}$ に重み ${A_i+B_j-M}$ の有向辺を張る( ${1\leq i\leq N}$ )．