本次题目全部来自卡码网
94. 城市间货物运输 I（Bellman_ford 队列优化算法）
bellman_ford使用队列优化
import collectionsclass Edge:def __init__(self, to, val):self.to = to # 链接的节点self.val = val # 边的权重if __name__ == '__main__':n, m = map(int, input().split())grid = [[] for _ in range(n + 1)] # 邻接表for i in range(m):p1, p2, val = map(int, input().split())grid[p1].append(Edge(p2, val))start = 1 # 起点end = n # 终点minDist = [float('inf')] * (n + 1)minDist[start] = 0que = collections.deque()que.append(start) # 队列里放入起点while que:node = que.popleft()for edge in grid[node]:_from = nodeto = edge.tovalue = edge.valif minDist[to] > minDist[_from] + value:minDist[to] = minDist[_from] + valueque.append(to)if minDist[end] == float('inf'):print('unconnected')else:print(minDist[end])95. 城市间货物运输 II（bellman_ford之判断负权回路）
检测负权回路
之前讲过的两种做法都能
第一种：松弛n-1次之后继续松弛，最短距离有变化，说明有负权回路，代码超时
第二种：加入队列>=n次，说明有负权回路
第一种
if __name__ == '__main__':n, m = map(int, input().split())grid = []for i in range(m):p1, p2, val = map(int, input().split())grid.append((p1, p2, val))start = 1 # 起点end = n # 终点minDist = [float('inf')] * (n + 1)minDist[start] = 0flag = Falsefor i in range(n): # 松弛n次，最后一次判断距离是否有变化for side in grid: # 每一次松弛，都是对所有边进行松弛_from = side[0] # 边的出发点to = side[1] # 边的到达点price = side[2] # 边的权值# 松弛操作# minDist[from] != INT_MAX 防止从未计算过的节点出发if i < n - 1:if minDist[_from] != float('inf') and minDist[to] > minDist[_from] + price:minDist[to] = minDist[_from] + priceelse:if minDist[_from] != float('inf') and minDist[to] > minDist[_from] + price:flag = Trueif flag:print('circle')elif minDist[end] == float('inf'):print("unconnected") # 不能到达终点else:print(minDist[end]) # 到达终点最短路径第二种
import collectionsclass Edge:def __init__(self, to, val):self.to = to # 链接的节点self.val = val # 边的权重if __name__ == '__main__':n, m = map(int, input().split())grid = [[] for _ in range(n + 1)] # 邻接表for i in range(m):p1, p2, val = map(int, input().split())grid[p1].append(Edge(p2, val))start = 1 # 起点end = n # 终点minDist = [float('inf')] * (n + 1)minDist[start] = 0count = [0] * (n + 1)flag = Falseque = collections.deque()que.append(start) # 队列里放入起点count[start] += 1while que:node = que.popleft()for edge in grid[node]:_from = nodeto = edge.tovalue = edge.valif minDist[to] > minDist[_from] + value:minDist[to] = minDist[_from] + valueque.append(to)count[to] += 1if count[to] == n:flag = Trueprint("circle")exit()if minDist[end] == float('inf'):print('unconnected')else:print(minDist[end])96. 城市间货物运输 III（bellman_ford之单源有限最短路）
至于经过k个节点
下面代码超时
if __name__ == '__main__':n, m = map(int, input().split())grid = []for i in range(m):p1, p2, val = map(int, input().split())grid.append((p1, p2, val))src, dst, k = map(int, input().split())minDist = [float('inf')] * (n + 1)minDist[src] = 0for i in range(k + 1):minDist_copy = minDist[:] # 获取上一次计算的结果for side in grid:_from = side[0]to = side[1]price = side[2]# 注意使用 minDist_copy 来计算 minDistif minDist_copy[_from] != float('inf') and minDist[to] > minDist_copy[_from] + price:minDist[to] = minDist_copy[_from] + priceif minDist[dst] == float('inf'):print("unreachable") # 不能到达终点else:print(minDist[dst]) # 到达终点最短路径下面代码可通过
import collectionsclass Edge:def __init__(self, to, val):self.to = to # 链接的节点self.val = val # 边的权重if __name__ == '__main__':n, m = map(int, input().split())grid = [[] for _ in range(n + 1)] # 邻接表for i in range(m):p1, p2, val = map(int, input().split())grid[p1].append(Edge(p2, val))start, end, k = map(int, input().split())k += 1minDist = [float('inf')] * (n + 1)minDist[start] = 0flag = Falseque = collections.deque()que.append(start) # 队列里放入起点while k != 0 and que:visited = [False] * (n + 1) # 每一轮松弛中，控制节点不用重复入队列minDist_copy = minDist[:] # 用来记录每一次遍历的结果que_size = len(que)for _ in range(que_size):node = que.popleft()for edge in grid[node]:_from = nodeto = edge.tovalue = edge.valif minDist[to] > minDist_copy[_from] + value:minDist[to] = minDist_copy[_from] + valueif visited[to]: # 不用重复放入队列，但需要重复松弛，所以放在这里位置continuevisited[to] = Trueque.append(to)k -= 1if minDist[end] == float('inf'):print('unreachable')else:print(minDist[end])
