1708: 数据结构-最短路径算法

解题思路:

注意事项:

参考代码:

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