公式解説ではベルマンフォード法による \(O(NM)\) 解法が示されていますが、グラフの構造に注目することで、ダイクストラ法を用いて \(O((N+M) \log N)\) で解くことができます。

1. グラフ \(G\) の構築と性質

公式解説の通り、この問題は以下のように差分制約を表現したグラフ \(G\) の最短路問題に帰着されます。

• 各 \(i=1,\dots,N\) について：
  • \(x_i - x_0 \le a_i + d_i\) （辺 \(0 \to i\), 重み \(a_i + d_i\)）
  • \(x_0 - x_i \le -a_i + d_i\) （辺 \(i \to 0\), 重み \(-a_i + d_i\)）
• 各 \(j=1,\dots,M\) について：
  • \(x_{u_j} - x_{v_j} \le e_j\) （辺 \(v_j \to u_j\), 重み \(e_j \ge 0\)）
  • \(x_{v_j} - x_{u_j} \le e_j\) （辺 \(u_j \to v_j\), 重み \(e_j \ge 0\)）

ここで重要なのは、重みが負になりうる辺は、始点または終点が頂点 \(0\) であるものに限られるという点です。

2. \(G'\) における最短距離の計算

\(G\) から「終点が頂点 \(0\) である辺」をすべて除去したグラフを \(G'\) とし、頂点 \(0\) からの最短距離を \(dist'(v)\) とします。

\(G'\) は「始点が頂点 \(0\) である負辺」を含み得ます。そこで、頂点 \(0\) から出るすべての辺の重みに一律で大きな定数 \(C\) を加え、計算後の距離から \(C\) を引くことで、すべての辺を非負として扱うことができます。これにより、ダイクストラ法を適用可能です。

なお、実はこのような工夫をせずとも、今回の \(G'\) の構造であれば通常のダイクストラ法をそのまま用いても問題なく計算できます。 負の重みを持つ辺は、始点が頂点 \(0\) であるものに限られ、頂点 \(0\) に戻る辺は \(G'\) に存在しません。したがって、最初のステップで頂点 \(0\) に隣接する各頂点の距離を更新した後は、負辺を含まないグラフに対する探索と全く同じ状況になります。

3. 負閉路の判定

\(G\) における負閉路の存在性は、以下の条件で判定できます。

ある除去された辺 \(v \to 0\)（重み \(w\)）が存在して、\(dist'(v) + w < 0\) となる。

4. 最短距離の正当性（\(dist = dist'\)）

負閉路が存在しない場合、元のグラフ \(G\) における最短距離 \(dist(v)\) は \(dist'(v)\) と一致します。

一般に、最短距離が定まっているグラフにおいて、ある辺 \(u \to v\)（重み \(w\)）を追加したとき、\(dist(u) + w \ge dist(v)\) が満たされていれば、最短距離は変化しません。

本問題では、負閉路がないならば \(dist'(v) + w \ge 0 = dist'(0) \) （ただし \(w\) は \(v \to 0\) の重み）が全ての除去された辺について成り立つため、これらを一本ずつ戻していっても \(dist'\) の値は変わりません。

5. 計算量

帰着後の各最短経路問題に対してダイクストラ法を適用することになり、全体の計算量は \(O((N+M) \log N)\) となります。