Bellman-Ford

Bellman-Ford算法可用于求解负权图的最短路问题，时间复杂度为O(mn)，劣于SPFA

对于访问边有频次限制的图求解最短路则只能使用Bellman-Ford算法

from copy import copy

# n 所有点的数量
# m 所有边的数量
# k 最大访问边数
n, m = [int(x) for x in input().split(" ")]

INF = 1e9

# dist
dist = [INF] * (n + 1)
dist[1] = 0

# backup
backup = [INF] * (n + 1)

edges = [[] for _ in range(m)]

for i in range(m):
    edges[i] = [int(x) for x in input().split(" ")]

#  如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，
#  由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for _ in range(n):
    backup = copy(dist)
    for i in range(m):
        a, b, w = edges[i]
        dist[b] = min(dist[b], backup[a] + w)

if dist[n] > INF / 2:
    print(-1)
else:
    print(dist[n])

边数限制的最短路问题

from copy import copy

# n 所有点的数量
# m 所有边的数量
# k 最大访问边数
n, m, k = [int(x) for x in input().split(" ")]

INF = 1e9

# dist
dist = [INF] * (n + 1)
dist[1] = 0

# backup
backup = [INF] * (n + 1)

edges = [[] for _ in range(m)]

for i in range(m):
    edges[i] = [int(x) for x in input().split(" ")]

for _ in range(k):
    backup = copy(dist)
    for i in range(m):
        a, b, w = edges[i]
        dist[b] = min(dist[b], backup[a] + w)

if dist[n] > INF / 2:
    print(-1)
else:
    print(dist[n])