更弱智的算法学习 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()