Ежедневный вопрос по алгоритму — leetcode 743 — время задержки в сети — python

алгоритм

【Название Описание】

【Анализ идей】

Когда вы интерпретируете вопросы, вы обнаружите, что на самом деле это проблема кратчайшего пути от нескольких точек к нескольким. Алгоритм Флойда является наиболее подходящим, и трехслойная петля может быть решена. Добавляйте по очереди промежуточные узлы и обновляйте матрицу расстояний. Дети, которые не знают Флойда, могут обратиться к этому:Подробное объяснение Флойда, временная сложность выше, чем куб 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])
Категории