代码随想录算法训练营第六十一天｜Bellman_ford 队列优化算法（又名SPFA）、bellman_ford之判断负权回路

卡码网：94. 城市间货物运输 I

from collections import dequeclass Edge:def __init__(self, to, val):self.to = to  # 链接的节点self.val = val  # 边的权重def main():n, m = map(int, input().split())grid = [list() for _ in range(n + 1)]  # 初始化邻接表for _ in range(m):p1, p2, val = map(int, input().split())grid[p1].append(Edge(p2, val))  # p1 指向 p2，权值为 valstart = 1  # 起点end = n    # 终点min_dist = [float('inf')] * (n + 1)  # 存储从起点到每个节点的最短距离min_dist[start] = 0que = deque([start])  # 使用双端队列存储已访问节点is_in_queue = [False] * (n + 1)  # 标记是否在队列中while que:node = que.popleft()is_in_queue[node] = False  # 从队列中移除节点for edge in grid[node]:to = edge.tovalue = edge.valif min_dist[to] > min_dist[node] + value:  # 开始松弛min_dist[to] = min_dist[node] + valueif not is_in_queue[to]:  # 如果节点不在队列中，则加入队列que.append(to)is_in_queue[to] = Trueif min_dist[end] == float('inf'):print("unconnected")  # 不能到达终点else:print(min_dist[end])  # 打印到达终点的最短路径长度if __name__ == "__main__":main()

卡码网：95. 城市间货物运输 II

from collections import dequeclass Edge:def __init__(self, to, val):self.to = to  # 链接的节点self.val = val  # 边的权重def main():n, m = map(int, input().split())grid = [list() for _ in range(n + 1)]  # 邻接表# 将所有边保存起来for _ in range(m):p1, p2, val = map(int, input().split())grid[p1].append(Edge(p2, val))  # p1 指向 p2，权值为 valstart = 1  # 起点end = n    # 终点min_dist = [float('inf')] * (n + 1)  # 存储从起点到每个节点的最短距离min_dist[start] = 0que = deque([start])  # 使用双端队列存储已访问节点count = [0] * (n + 1)  # 记录节点加入队列几次count[start] = 1flag = Falsewhile que:node = que.popleft()for edge in grid[node]:to = edge.tovalue = edge.valif min_dist[to] > min_dist[node] + value:  # 开始松弛min_dist[to] = min_dist[node] + valueque.append(to)count[to] += 1if count[to] == n:  # 如果加入队列次数超过 n-1次 就说明该图与负权回路flag = Truebreakif flag:breakif flag:print("circle")elif min_dist[end] == float('inf'):print("unconnected")else:print(min_dist[end])if __name__ == "__main__":main()