Участник:Plague rat/Network Delay Time

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/network-delay-time/

class Solution:
    def networkDelayTime(self, times: List[List[int]], N: int, K: int) -> int:
        graph = [[] for i in range(N)]
        for edge in times:
            graph[edge[0] - 1].append(tuple([edge[1] - 1, edge[2]]))
 
        distances = [10 ** 9] * N
        distances[K - 1] = 0
        visited = [False] * N
        for i in range(N):
            v = -1
            for j in range(N):
                if not visited[j] and (v == -1 or distances[j] < distances[v]):
                    v = j
            if distances[v] == 10 ** 9:
                break
            visited[v] = True
            for j in range(len(graph[v])):
                to = graph[v][j][0]
                _len = graph[v][j][1]
                if distances[v] + _len < distances[to]:
                    distances[to] = distances[v] + _len
 
        if False in visited:
            return -1
        else:
            return max(distances)