更弱智的算法学习 day60

Bellman_ford 队列优化算法import collections def main(): n, m map(int, input().strip().split()) edges [[] for _ in range(n 1)] for _ in range(m): src, dest, weight map(int, input().strip().split()) edges[src].append([dest, weight]) minDist [float(inf)] * (n 1) minDist[1] 0 que collections.deque([1]) visited [False] * (n 1) visited[1] True while que: cur que.popleft() visited[cur] False for dest, weight in edges[cur]: if minDist[cur] ! float(inf) and minDist[cur] weight minDist[dest]: minDist[dest] minDist[cur] weight if visited[dest] False: que.append(dest) visited[dest] True if minDist[-1] float(inf): return unconnected return minDist[-1] if __name__ __main__: print(main())bellman_ford之判断负权回路import sys def main(): input sys.stdin.read data input().split() index 0 n int(data[index]) index 1 m int(data[index]) index 1 grid [] for i in range(m): p1 int(data[index]) index 1 p2 int(data[index]) index 1 val int(data[index]) index 1 # p1 指向 p2权值为 val grid.append([p1, p2, val]) start 1 # 起点 end n # 终点 minDist [float(inf)] * (n 1) minDist[start] 0 flag False for i in range(1, n 1): # 这里我们松弛n次最后一次判断负权回路 for side in grid: from_node side[0] to side[1] price side[2] if i n: if minDist[from_node] ! float(inf) and minDist[to] minDist[from_node] price: minDist[to] minDist[from_node] price else: # 多加一次松弛判断负权回路 if minDist[from_node] ! float(inf) and minDist[to] minDist[from_node] price: flag True if flag: print(circle) elif minDist[end] float(inf): print(unconnected) else: print(minDist[end]) if __name__ __main__: main()bellman_ford之单源有限最短路def main(): # 輸入 n, m map(int, input().split()) edges list() for _ in range(m): edges.append(list(map(int, input().split() ))) start, end, k map(int, input().split()) min_dist [float(inf) for _ in range(n 1)] min_dist[start] 0 # 只能經過k個城市所以從起始點到中間有(k 1)個邊連接 # 需要鬆弛(k 1)次 for _ in range(k 1): update False min_dist_copy min_dist.copy() for src, desc, w in edges: if (min_dist_copy[src] ! float(inf) and min_dist_copy[src] w min_dist[desc]): min_dist[desc] min_dist_copy[src] w update True if not update: break # 輸出 if min_dist[end] float(inf): print(unreachable) else: print(min_dist[end]) if __name__ __main__: main()