743.md

743. Network Delay Time

Solution 1 (time O(n^2), space O(n^2))

# Dijkstra
class Solution(object):
    def networkDelayTime(self, times, n, k):
        """
        :type times: List[List[int]]
        :type n: int
        :type k: int
        :rtype: int
        """
        g = [[float("inf") for _ in range(n)] for _ in range(n)]
        for u, v, w in times:
            g[u - 1][v - 1] = w
        for i in range(n):
            g[i][i] = 0
        dist = [g[k - 1][i] for i in range(n)]
        vis = [False for _ in range(n)]
        vis[k - 1] = True
        for _ in range(n - 1):
            min_dist = float("inf")
            new_node = -1
            for i in range(n):
                if vis[i]:
                    continue
                if dist[i] < min_dist:
                    min_dist = dist[i]
                    new_node = i
            if new_node == -1:
                break
            vis[new_node] = True
            for i in range(n):
                if vis[i]:
                    continue
                dist[i] = min(dist[i], dist[new_node] + g[new_node][i])
        ans = max(dist)
        return -1 if ans == float("inf") else ans