743

class Solution {
public:
    typedef pair<int, int> T;
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<T>> graph(n+1);
        for(auto edge:times){
            graph[edge[0]].push_back({edge[1], edge[2]});
        }

        vector<int> dist(n+1, INT_MAX);
        priority_queue<T, vector<T>, greater<>> pq;
        dist[k] = 0;
        pq.push({dist[k], k});

        while(!pq.empty()){
            auto node = pq.top(); pq.pop();
            if(dist[node.second] < node.first) continue;
            for(auto edge: graph[node.second]){
                if(dist[edge.first] > node.first+edge.second){
                    dist[edge.first] = node.first+edge.second;
                    pq.push({dist[edge.first], edge.first});
                }
            }
        }
        int ans = 0;
        for(int i=1; i<=n; i++)
            ans = max(ans, dist[i]);
        if(ans == INT_MAX) ans = -1;
        return ans;
    }
};