Bellman-Ford算法 例题：P3371 单源最短路径

看到还没人用Bellman-Ford过，赶紧水一发
lz非常弱，求各位大佬轻喷qwq
洛谷题目传送门：P3371
0.“松弛”操作
如果存在一条边/((u,v)/)通过中继的方式可以让起点到/(v/)的距离缩短，那么就通过中继点缩短这个距离。
举个栗子：

(用数组/(dis[]/)来表示起点到每个点的距离，以下同样)
一开始，/(dis[2]=1000/)，/(dis[3]=2/)(默认起点为1,以下同样)
通过3中继明显比从1直接到2要短，于是我们把/(dis[2]/)更新为/(dis[3]+3=5/)(从起点到3再到5)
于是你理解了什么是松弛
1.Bellman-Ford
Bellman-Ford的思想是用每条边进行松弛，每条边松弛/(n-1/)次，就一定能求出起点到每个点的距离
(如果你能感性理解你就不用看下面了)
为什么？因为每松弛1轮(我们管用每条边都松弛一次叫一轮)，最短路就至少“生长”1个点。
再举个例子：

这是个很美丽的有向图。
最开始，除了/(

Bellman-Ford算法 例题：P3371 单源最短路径最先出现在Python成神之路。