【LeetCode刷題（中等程度）】743. 網絡延遲時間

題目連結：743. 網絡延遲時間

參考最短路徑算法：最短路徑算法通俗易懂了解

思路：找到每個點到k點的最短距離，因為傳播是同時的，是以我們找到這些最短路徑的最大值即可。

代碼：

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        queue<int>myQue;//用于即将通路的節點
        //distToK[index]表示點K到點index的最短距離
        vector<int> distToK(n + 1,INT_MAX);
        vector<vector<int>> graph(n+1,vector<int>(n+1,-1));//鄰接矩陣
        for(auto &time : times) {
            graph[time[0]][time[1]] = time[2];//注意是有向圖
        }

        myQue.push(k);//從k開始
        distToK[k] = 0;//K到自己的最短距離為0
        //開始搜尋各個點到k的最短距離
        while(!myQue.empty()) {
            int front = myQue.front();
            myQue.pop();

            //利用目前front節點嘗試稀疏點k到所有節點的最短距離
            for(int target = 1;target <= n;++target) {
                if (graph[front][target] != -1 && 
                    distToK[front] + graph[front][target] < distToK[target]){
                //如果front到target有邊，并且點k到front的距離distToK[front] + 
                //點front到target距離graph[front][target]小于點k到target的距離distToK[target]
                    distToK[target] = distToK[front] + graph[front][target];//則進行更新
                    myQue.push(target);//放入隊列
                }
            }
        }
        //尋找點k到各個點的最短距離的最大值
        int maxRes = 0;
        for(int i = 1; i <= n; ++i){
            maxRes = max(maxRes, distToK[i]);
        }
        return maxRes == INT_MAX? -1 : maxRes;
    }
};