【代码随想录算法训练营第六十五天|卡码网94.城市间货物运输I&II&III】

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')