###### tags: `Leetcode` `medium` `graph` `heap` `bfs` `python` `c++`

# 743. Network Delay Time

## [題目連結:] https://leetcode.com/problems/network-delay-time/

## 題目:
You are given a network of ```n``` nodes, labeled from ```1``` to ```n```. You are also given ```times```, a list of travel times as directed edges ```times[i] = (ui, vi, wi)```, where ```ui``` is the source node, ```vi``` is the target node, and ```wi``` is the time it takes for a signal to travel from source to target.

We will send a signal from a given node ```k```. Return the **minimum** time it takes for all the n nodes to receive the signal. If it is impossible for all the ```n``` nodes to receive the signal, return ```-1```.


## 解題想法:
* 此題為給n個節點，標記為1到n
* 給一列表times: times[i] = (ui, vi, wi)
* ui:起始點
* vi:結尾點
* wi:傳遞時間(權重)
* 求某點k發出信號，多快能使所有節點均能收到
* 若不能使所有節點收到，return -1

* **Dijkstra**: 單源最短路徑(單個點到任一點的最短路徑)
* 使用限制:
* 權重不可有負
* 不能出現負環
* 流程:
* Step1: 建立邊

    edge=defaultdict(list)
    for i in range(len(times)):
        u,v,weight=times[i]
        edge[u].append((v,weight))
    '''
    表示: u--------->v
            weight
    '''

* Step2: 初始需要用的工具
* visited=set() :紀錄已拜訪過的點
* que=[(0,k)]: (距離,點)
* que使用**heap**，因為可以pop出來每次距離最短的
* Step3: BFS遍歷que
* 1. heapque每次選出que中權重最小的出來
* 2. 判斷是否已拜訪過
* 3. 將當前權重更新其連接的鄰居節點，並將鄰居節點加入que

    while que:
        cur_dis,node=heappop(que) #pop出最短距離的更新
        if node in visited:
            continue
        visited.add(node)
        if len(visited)==n:
            return cur_dis #最後pop出來 且不重複 表示他是最遠點中最短ㄉ距離
        for neiber,weight in edge[node]:
            heappush(que,(cur_dis+weight,neiber))
    return -1

## Python:
* **heapq**:為min_heap

from collections import defaultdict
from heapq import heappop, heappush
class Solution(object):
    def networkDelayTime(self, times, n, k):
        """
        :type times: List[List[int]]
        :type n: int
        :type k: int
        :rtype: int
        """
        #用dijkstra
        #建立邊
        edge=defaultdict(list)
        for i in range(len(times)):
            u,v,weight=times[i]
            edge[u].append((v,weight))
        #bfs: 找與k最遠點的最短距離
        visited=set() #紀錄已拜訪過的點
        #用heap來裝 因為可以pop出來每次距離最短的
        que=[(0,k)] #(距離,點)
        while que:
            cur_dis,node=heappop(que) #pop出最短距離的更新
            if node in visited:
                continue
            visited.add(node)
            if len(visited)==n:
                return cur_dis #最後pop出來 且不重複 表示他是最遠點中最短ㄉ距離
            for neiber,weight in edge[node]:
                heappush(que,(cur_dis+weight,neiber))
        return -1

times =[[1,2,1],[2,3,2],[1,3,4]]
n=3
k=1
result=Solution()
ans=result.networkDelayTime(times,n,k)
print(ans)

## C++:
* priority_queue:為max_heap
* 最頂端要用top()，而非front()

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        unordered_map<int, vector<pair<int, int>> > edge;
        //connected the graph
        for (int i=0; i<times.size(); i++){
            int u=times[i][0], v=times[i][1], w=times[i][2];
            edge[u].push_back({v,-w});
        }
        set<int> visited;
        priority_queue<pair<int, int>> que; //max_heap
        que.push({0,k});
        //bfs
        while (!que.empty()){
            pair<int, int> curItem=que.top(); que.pop();
            int curDis=curItem.first, node=curItem.second;
            if (visited.count(node)) // if node already exist in visited
                continue;
            visited.insert(node);
            if (visited.size()==n)
                return -curDis;
            //upload neighber
            for (auto item: edge[node]){
                int neighber=item.first, weight=item.second;
                que.push({(curDis+weight), neighber});
            }
        }
        return -1;
    }
};