【题目描述】
【思路解析】解读题干会发现,其实就是一道多点到多点的最短路径问题,用floyd算法最合适,三层循环就搞定。依次加入中间节点,并更新距离矩阵。不了解floyd的小朋友可以参考这篇:floyd详解,时间复杂度比较高n的立方。
【源代码】
class Solution:
def networkDelayTime(self, times, N, K):
arr=[[float('inf') for _ in range(N)]for _ in range(N)]
for t in times:
x=t[0]-1
y=t[1]-1
arr[x][y]=t[2]
for i in range(N):
arr[i][i]=0
for k in range(N):
for i in range(N):
for j in range(N):
if arr[i][j]>arr[i][k]+arr[k][j]:
arr[i][j]=arr[i][k]+arr[k][j]
if float('inf') in arr[K-1]:
return -1
return max(arr[K-1])
复制代码