743. Network Delay Time

解題心得

Dijkstra 演算法實作。

1. emplace_back 會把該筆資料放到最末端；emplace 是放入任意位置。

2. 用 minHeap，是因為在演算法中，要取出當下 cost 最小的路徑來做更新。

3. 用 max()，是因為找出傳到所有 node 最少需要的時間，又最遠 node 要得最久。

4. 如果無法每個 node 都拜訪，則回傳 -1。

程式碼

typedef pair<int, int> edge; // target node, weight;

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<edge>> graph(n+1);
        for(int i=0; i<times.size(); i++)
            graph[times[i][0]].emplace_back(times[i][1], times[i][2]);
        
        priority_queue<edge, vector<edge>, greater<edge>> minHeap;
        vector<bool> isVisited(n+1, false);
        minHeap.emplace(0, k);
        int ans = 0;
        while(!minHeap.empty())
        {
            int w1, n1;
            w1 = minHeap.top().first, n1 = minHeap.top().second;
            minHeap.pop();
            if(isVisited[n1])
                continue;
            isVisited[n1] = true;
            ans = max(ans, w1);

            for(int i=0; i<graph[n1].size(); i++)
            {
                int w2 = graph[n1][i].second, n2 = graph[n1][i].first;
                if(!isVisited[n2])
                    minHeap.emplace(w1 + w2, n2);
            }
        }
        for(int i=1; i<=n; i++)
        {
            if(!isVisited[i])
                return -1;
        }
        return ans;
    }
};