差分約束系統定義
形如 Xi - Xj ≤ c 的不等式組。解要麼無解，要麼無限多解（整體平移不變差值）。
圖論轉化
- 每個變量 Xi ↔ 頂點 Vi
- 不等式 Xi - Xj ≤ c ↔ 有向邊 Vj → Vi，權值 c
- 引入超級源點 V0，連向所有點，權值 0
- 求單源最短路徑，距離即為一組解
關鍵性質
- 最短路三角不等式 d(v) ≤ d(u) + w(u,v) 恰好對應差分約束
- 負權環 ⇔ 無解
- 固定源點距離為 0 時，求得的解使所有變量取最大值
- 求最小值需轉為最長路（初始化 -∞，邊權取反）
SPFA 實現
