@[codingxile](/user/377794) 要建超级源点
by liangbowen @ 2022-07-31 10:27:29
首先负权边也是要建的，把
```cpp
if(w>=0)
{
add(v,u,w);
}
```
直接改成 `add(v, u, w)`
by liangbowen @ 2022-07-31 10:28:43
楼上正解
by Orange_qwq @ 2022-07-31 10:29:59
`cout<<dis[i]<<'1';` 这输出是啥，还要建超级源点，图不保证联通
by naroanah @ 2022-07-31 10:30:15
@[codingxile](/user/377794) 多弄一个节点 $0$，然后由节点 $0$ 向节点 $1, 2, \ldots , n$ 各连一条长度为 $0$ 的边。SPFA 时直接把节点 $0$ 丢进队列即可，即以 $0$ 作为起点。
by huangkx @ 2022-07-31 10:31:08
其次，这样建完后，图可能不连通。为了使得图连通，我们假设超级源点是 $0$（本来是不存在的QwQ），建边：
```cpp
for (int i = 1; i <= n; i++) add(0, i, 0);
```
边权是 $0$，简单说就是：边是空气。
然后把存边的 `e` 数组开大一点
by liangbowen @ 2022-07-31 10:31:46
@[liangbowen](/user/367488)
所以我得建负权边和超级源点吧
by Level_1024 @ 2022-07-31 10:34:15
@[codingxile](/user/377794) 我就是这个意思呀，肯定得建
您代码就没有建
by liangbowen @ 2022-07-31 10:35:27
@[liangbowen](/user/367488) 哦，好的，thx
by Level_1024 @ 2022-07-31 10:36:06
还有 `add(u,v,w);` 完全不需要
建议再学学差分约束，看第一篇题解
您显然没有理解三角不等式的转化，只用 `add(v, u, w)` 就够了。
---
最短路三角不等式：$dis_u + w_{u \to v} \ge dis_v$。
约束条件中，$x_{a}-x_{b} \leq w$ 可以转化为 $x_{b} + w \ge x_{a}$
这两者看起来一模一样，于是类似地，只需连接 $b_i \to a_i$，长度为 $w_i$。
---
题解比我现在讲得好多了 QwQ
by liangbowen @ 2022-07-31 10:39:40