一般的转化不等式 + 建图 + 判断负环不加赘述
图是否连通
如果图不连通, 那么证明约束条件并不能全部约束
有两种办法解决这个问题
- 建超级源点
- 将每个点作为起点跑
求 dis 的最大值 / 最小值
对于 Intervals
最后考虑求 \(dis\) 的最大值
对于 Layout G , 和 Capitalism
最后要求 \(dis\) 的最小值
考虑最短路的不等式形式
对于边 \((u, v, w)\) , 有 \(dis_v \leq dis_u + w\)
那么对于点 \(u\) 来说 , 现在的 \(dis\) 表示从 \(1\) 开始的最短路