目录
Bellman_ford 队列优化算法
- 题目链接：卡码网：94. 城市间货物运输 I
文章讲解：代码随想录
某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。
网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。
权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。
请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。
如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。
城市 1 到城市 n 之间可能会出现没有路径的情况，同时保证道路网络中不存在任何负权回路。
负权回路是指一系列道路的总权值为负，这样的回路使得通过反复经过回路中的道路，理论上可以无限地减少总成本或无限地增加总收益。
输入描述
第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。
接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v（单向图）。
输出描述
如果能够从城市 1 到连通到城市 n， 请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 "unconnected"。
输入示例：
6 7 5 6 -2 1 2 1 5 3 1 2 5 2 2 4 -3 4 6 4 1 3 5
思路
Bellman_ford 算法每次松弛 都是对所有边进行松弛。
但真正有效的松弛，是基于已经计算过的节点在做的松弛。
给大家举一个例子：
本图中，对所有边进行松弛，真正有效的松弛，只有松弛 边（节点1->节点2） 和 边（节点1->节点3） 。
而松弛 边（节点4->节点6） ，边（节点5->节点3）等等 都是无效的操作，因为 节点4 和 节点 5 都是没有被计算过的节点。
所以 Bellman_ford 算法 每次都是对所有边进行松弛，其实是多做了一些无用功。
只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛就够了。
基于以上思路，如何记录 上次松弛的时候更新过的节点呢？
用队列来记录。（其实用栈也行，对元素顺序没有要求）
模拟过程
接下来来举例这个队列是如何工作的。
以示例给出的所有边为例：
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5
我们依然使用minDist数组来表达 起点到各个节点的最短距离，例如minDist[3] = 5 表示起点到达节点3 的最小距离为5
初始化，起点为节点1， 起点到起点的最短距离为0，所以minDist[1] 为 0。 将节点1 加入队列 （下次松弛从节点1开始）
从队列里取出节点1，松弛节点1 作为出发点连接的边（节点1 -> 节点2）和边（节点1 -> 节点3）
边：节点1 -> 节点2，权值为1 ，minDist[2] > minDist[1] + 1 ，更新 minDist[2] = minDist[1] + 1 = 0 + 1 = 1 。
边：节点1 -> 节点3，权值为5 ，minDist[3] > minDist[1] + 5，更新 minDist[3] = minDist[1] + 5 = 0 + 5 = 5。
将节点2、节点3 加入队列，如图：
从队列里取出节点2，松弛节点2 作为出发点连接的边（节点2 -> 节点4）和边（节点2 -> 节点5）
边：节点2 -> 节点4，权值为1 ，minDist[4] > minDist[2] + (-3) ，更新 minDist[4] = minDist[2] + (-3) = 1 + (-3) = -2 。
边：节点2 -> 节点5，权值为2 ，minDist[5] > minDist[2] + 2 ，更新 minDist[5] = minDist[2] + 2 = 1 + 2 = 3 。
将节点4，节点5 加入队列，如图：
从队列里出去节点3，松弛节点3 作为出发点连接的边。
因为没有从节点3作为出发点的边，所以这里就从队列里取出节点3就好，不用做其他操作，如图：
从队列中取出节点4，松弛节点4作为出发点连接的边（节点4 -> 节点6）
边：节点4 -> 节点6，权值为4 ，minDist[6] > minDist[4] + 4，更新 minDist[6] = minDist[4] + 4 = -2 + 4 = 2 。
将节点6加入队列
如图：
从队列中取出节点5，松弛节点5作为出发点连接的边（节点5 -> 节点3），边（节点5 -> 节点6）
边：节点5 -> 节点3，权值为1 ，minDist[3] > minDist[5] + 1 ，更新 minDist[3] = minDist[5] + 1 = 3 + 1 = 4
边：节点5 -> 节点6，权值为-2 ，minDist[6] > minDist[5] + (-2) ，更新 minDist[6] = minDist[5] + (-2) = 3 - 2 = 1
如图，将节点3加入队列，因为节点6已经在队列里，所以不用重复添加
所以我们在加入队列的过程可以有一个优化，用isInque数组记录已经在队列里的元素，已经在队列的元素不用重复加入
从队列中取出节点6，松弛节点6 作为出发点连接的边。
节点6作为终点，没有可以出发的边。
同理从队列中取出节点3，也没有可以出发的边
所以直接从队列中取出，如图：
这样我们就完成了基于队列优化的bellman_ford的算法模拟过程。
大家可以发现 基于队列优化的算法，要比bellman_ford 算法 减少很多无用的松弛情况，特别是对于边数众多的大图 优化效果明显。
了解了大体流程，我们再看代码应该怎么写。
在上面模拟过程中，我们每次都要知道 一个节点作为出发点连接了哪些节点。
如果想方便知道这些数据，就需要使用邻接表来存储这个图，如果对于邻接表不了解的话，可以看 kama0047.参会dijkstra堆 中 图的存储 部分。
方法一：Bellman_ford 队列优化
from collections import deque
class Edge:
def __init__(self,to,val) -> None:
self.to = to
self.val = val
def main():
n,m = map(int,input().split())
grid = [[] for _ in range(n+1)]
for i in range(m):
start,end,val = map(int,input().split())
grid[start].append(Edge(end,val))
start = 1
end = n
que = deque()
que.append(1)
isInque = [False] * (n+1)
isInque[start] = True
minDist = [float('inf')] * (n+1)
minDist[start] = 0
while que:
cur_node = que.popleft()
isInque[cur_node] = False
for edge in grid[cur_node]:
if minDist[cur_node] + edge.val < minDist[edge.to]:
minDist[edge.to] = minDist[cur_node] + edge.val
if not isInque[edge.to] :
que.append(edge.to)
isInque[edge.to] = True
print('unconnected') if minDist[end] == float('inf') else print(minDist[end])
if __name__ == "__main__":
main()