94.城市间货物运输I
SPFA(bellman_ford队列优化)
在bellman_ford的基础上,在每次松弛的时候,只有和前面的结点相连的边的松弛才是有效的,因此可以引入一个队列存储已经访问过的结点,针对连接这些结点的边进行松弛。
from collections import deque
n, m = map(int, input().split())
grid = [[] for _ in range(n+1)]
for i in range(m):
s, t, v = map(int, input().split())
grid[s].append([t, v])
start = 1
end = n
minDist = [float('inf')] * (n + 1)
minDist[1] = 0
queue = deque()
queue.append(start)
while queue:
cur = queue.popleft()
for edge in grid[cur]:
if minDist[edge[0]] > minDist[cur] + edge[1]:
minDist[edge[0]] = minDist[cur] + edge[1]
queue.append(edge[0])
if minDist[end]!=float('inf'):
print(minDist[end])
else:
print('unconnected')
Bellman_ford判断负权回路
如果没有负权回路,第n次更新所有minDist都不会变,但是存在负权回路的话就会变,所以进行n次的b_f,最后一步看是否有变化,有的话说明存在负权重回路。
n, m = map(int, input().split())
grid = []
for i in range(m):
s, t, v = map(int, input().split())
grid.append([s, t, v])
start = 1
end = n
minDist = [float('inf')] * (n + 1)
minDist[1] = 0
updated = False
for i in range(n):
for edge in grid:
if minDist[edge[0]]!=float('inf') and minDist[edge[1]] > minDist[edge[0]] + edge[2]:
if i < n - 1:
minDist[edge[1]] = minDist[edge[0]] + edge[2]
else:
updated = True
if updated:
print('circle')
elif minDist[end]!=float('inf'):
print(minDist[end])
else:
print('unconnected')
96.城市间货物运输III
Bellman_ford
限制经过K个城市那就是限制最多k+1条边,Bellman_ford算法松弛k+1次即可。还有一个要注意的是,正常B_F松弛在同一组松弛的时候,前一个松弛的边是可能对后续的边产生影响的,正常B_F是无所谓因为可以超过n-1次也不影响,但是在这里就需要注意,用来判断是否要更新距离是用上一次松弛完的结果来判断,但是松弛结果更新在这一次的结果中。
n, m = map(int, input().split())
grid = []
for i in range(m):
s, t, v = map(int, input().split())
grid.append([s, t, v])
src, dst, k = map(int, input().split())
start = src
end = dst
minDist = [float('inf')] * (n + 1)
minDist[start] = 0
minDist_last = [float('inf')] * (n + 1)
for i in range(k+1):
minDist_last = minDist
for edge in grid:
if minDist_last[edge[0]]!=float('inf') and minDist_last[edge[1]] > minDist_last[edge[0]] + edge[2]:
minDist[edge[1]] = minDist[edge[0]] + edge[2]
if minDist[end]!=float('inf'):
print(minDist[end])
else:
print('unreachable')