Dijkstra's Algorithm

• use Dijkstra's algorithm to find the shortest path from our source to all targets. - O(n^2)
• actually, use Heap to replace Queue in BFS - O(nlogn)
• 边的权重不能为负

743. Network Delay Time

class Solution(object):
    def networkDelayTime(self, times, N, K):
        graph = [[] for _ in xrange(N+1)]
        for u, v, w in times:
            graph[u].append((v, w))

        dis = [0] + [-1] * N  
        pq = [(0, K)]

        while pq:
            w, s = heapq.heappop(pq)
            if dis[s] >= 0:
                continue
            dis[s] = w
            for nxt, nw in graph[s]:
                heapq.heappush(pq, (w+nw, nxt))
        return -1 if -1 in dis else max(dis)