day60

Bellman_ford 队列优化算法：
Bellman_ford 算法每次松弛 都是对所有边进行松弛。但真正有效的松弛，是基于已经计算过的节点在做的松弛；队列优化算法只对 上一次松弛的时候更新过的节点作为出发节点所连接的边 进行松弛，用队列来记录上次松弛的时候更新过的节点。
已经在队列里的元素不用重复添加，而从队列里取出的时候，要取消标记。这是因为每个要加入队列的节点，都是一次松弛后得到了更小距离的节点，以它作为出发节点的边也可以获得更小距离。所以如果此时该节点已经再队列里，没有必要再加一次，因为它还没出队更新，一旦出队就会更新好当前情况下的最小距离，但是从队列取出时要取消标记，因为可能该节点的最小距离还会得到更新（找到其它节点到它的路最短），那么以它为出发节点的边也要进行更新！

bellman_ford判断负权回路：
在有负权回路的情况下，一直都会有更短的最短路，所以松弛第n次，minDist数组也会发生改变
所以判断是否有负权回路，就是在松弛n-1次的基础上再多松弛一次，看minDist数组是否发生变化

bellman_ford单源有限最短路：
计算在最多经过 k 个城市的条件下，从城市 src 到城市 dst 的最低运输成本，最多经过 k 个城市， 那么是 k + 1条边相连的节点，所以本题就是求：起点最多经过k + 1 条边到达终点的最短距离。
根据之前对所有边松弛一次，相当于计算 起点到达 与起点一条边相连的节点 的最短距离得知：对所有边松弛 k + 1次，就是求 起点到达 与起点k + 1条边相连的节点的 最短距离。在有负权回路的情况下，还需要注意使用上次的minDist数组