AcWing 854. Floyd求最短路
原题链接
简单
作者:
不知名_4
,
2024-07-25 19:04:11
,
所有人可见
,
阅读 1
弗洛伊德Floyd最短路
Python 代码
"""
图中可能存在重边和自环,边权可能为负数。
"""
n,m,k = map(int,input().split())
# 节点序号从1开始
dist = [[float('inf') for i in range(n+1)]for j in range(n+1)]
path = [[-1 for i in range(n+1)]for j in range(n+1)]
# 根据提交样例要求 自己到自己的距离为0 !!!!!!
for i in range(1,n+1):
dist[i][i] = 0
for i in range(m):
u,v,w = map(int,input().split())
if w < dist[u][v]:
dist[u][v] = w
# print(dist)
for i in range(1,n+1):
for a in range(1,n+1):
for b in range(1,n+1):
if a != i and b!=i and a!=b:
if dist[a][b] > dist[a][i] + dist[i][b]:
# 即使a到i节点之间还有其他节点,但是根据动态规划思想,
# 这里dist[a][i]也已经是最优,无需再考虑
dist[a][b] = dist[a][i] + dist[i][b]
path[a][b] = i
# print(dist)
for _ in range(k):
start,end = map(int,input().split())
if dist[start][end]==float('inf'):
print("impossible")
else:
print(dist[start][end])