思路
用邻接矩阵存储边
Floyd是基于动态规划的,d[k, i, j] 表示从节点 i 出发,只经过 1 ~ k 节点到达节点 j 的最短距离,
然后用 d[k - 1, i, k] + d[k - 1, k, j] 更新 d[k, i, j],其中第一维可以省去
判断 a 到 b 的距离使用 dmax // 2,是因为距离可能会因为负权边的存在而从 dmax降低,所以不能使用等于号进行判断,而使用一个与dmax相同数量级的数字进行判断。
代码 + 注释
n, m, k = map(int, input().split())
N = n + 1
dmax = 1 << 30
d = [[dmax] * N for _ in range(N)]
for i in range(1, n + 1):
d[i][i] = 0
for i in range(m):
a, b, c = map(int, input().split())
d[a][b] = min(d[a][b], c)
def floyd():
for k in range(1, n + 1):
for i in range(1, n + 1):
for j in range(1, n + 1):
d[i][j] = min(d[i][j], d[i][k] + d[k][j])
# d[k, i, j] 表示从节点 i 出发,只经过 1 ~ k 节点到达节点 j 的最短距离
# d[k - 1, i, k] + d[k - 1, k, j] 更新 d[k, i, j]
# 第一维可以省略
return
floyd()
for i in range(k):
a, b = map(int, input().split())
if d[a][b] > dmax // 2:
print("impossible")
else:
print(d[a][b])
可以用float(“inf”),这样就可以用==判断了。个人觉得会舒服一些