Python3_Floyd最短路
作者:
成理第一深情
,
2024-01-29 12:48:59
,
所有人可见
,
阅读 50
"""
floyd算法:
求解多源汇最短路问题
三重循环
"""
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])
n, m, k = map(int, input().strip().split())
# 初始化d
d = [[float("inf")] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
d[i][i] = 0
for i in range(m):
x, y, z = map(int, input().strip().split())
d[x][y] = min(d[x][y], z)
floyd()
for i in range(k):
x, y = map(int, input().strip().split())
if d[x][y] == float("inf"):
print("impossible")
else:
print(d[x][y])