# 743. Network Delay Time

## 想法
Dijkstra's algorithm模板題
## 演算法

/*
1. 建構圖
2. 使用Dijkstra's algorithm找出從k出發的最短路徑，放在陣列d中
3. 找到d中的最大值maxV，若maxV為MAXIMUM，則回傳-1，否則回傳maxV
*/
/*
Dijkstra's algorithm
1. 初始化d陣列,pq, done陣列
2. 將d[s]設為0，並推入pq
3. while !pq.empty():
    3.1. u = pq.top; pq.pop();
    3.2. 若u已經做完了，continue，否則，done[u]=1
    3.3. for every v = adj[u]:
        3.3.1. 若v還沒做完，且從s走到u再走到v會比s走到v還要短，則更新d[v]，並將d[v]推入pq中

*/

## 程式碼

#define ll long long
class Solution {
public:
    vector <ll> dijkstra(vector <vector <pair <ll, ll>>> &adj, ll n, ll s) {
        vector <ll> d(n + 1, LONG_LONG_MAX);
        priority_queue <pair <ll, ll>, vector <pair <ll, ll>>, greater <pair <ll, ll>>> pq;
        vector <ll> done(n + 1);
        d[s] = 0;
        pq.push({0, s});
        while (!pq.empty()) {
            pair <ll, ll> tmp = pq.top();
            ll u = tmp.second;
            pq.pop();
            if (done[u]) continue;
            done[u] = 1;
            for (auto it = adj[u].begin(); it != adj[u].end(); it++) {
                ll v = it -> first, w = it -> second;
                if (!done[v]) {
                    if (d[v] > d[u] + w) {
                        d[v] = d[u] + w;
                        pq.push({d[v], v});
                    }
                }
            }
        }
        return d;
    }

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector <vector <pair <ll, ll>>> adj(n + 1, vector <pair <ll, ll>>());
        for (int i = 0; i < times.size(); i++) {
            ll u = times[i][0], v = times[i][1], w = times[i][2];
            adj[u].push_back({v, w});
        }    
        vector <ll> d = dijkstra(adj, n, k);
        ll maxV = LONG_LONG_MIN;
        for (int i = 1; i <= n; i++) {
            maxV = max(maxV, d[i]);
        }
        if (maxV == LONG_LONG_MAX) {
            return -1;
        } else {
            return maxV;
        }
    }
};