(fly)1709: 数据结构-Floyd(弗洛伊德)最短路径算法(python)

解题思路:

注意事项:

参考代码:

n=int(input())
inf=float('inf')
dp=[]
for i in range(n):
    dp.append(list(map(int,input().split())))
#print(dp)
for i in range(n):
    for j in range(n):
        if i!=j and dp[i][j]==0:
            dp[i][j]=inf 
#print(dp)
for i in range(n):
    for j in range(n):
        for k in range(n):
            if dp[j][k]>dp[j][i]+dp[i][k]:
                dp[j][k]=dp[j][i]+dp[i][k]
#print(dp)
for i in range(n):
    for j in range(n):
        if dp[i][j]==inf:
            dp[i][j]=-1
for i in dp:
    for j in i:
        print(j,end=' ')
    print()