Description

Submission

class Solution {
    typedef pair<int, int> PII;
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<PII>> graph(n+1);

        for(auto& t: times) {
            graph[t[0]].push_back({t[1], t[2]});
        }

        priority_queue<PII, vector<PII>, greater<PII>> pq;  // distance, node id
        pq.emplace(0, k);

        vector<int> visited(n+1, 0);

        int ret = 0;
        while(!pq.empty()) {
            auto [dist, cur] = pq.top();
            pq.pop();

            if(visited[cur]) continue;
            visited[cur] = 1;

            ret = max(ret, dist);

            for(auto [id, d]: graph[cur]) {

                if(visited[id]) continue;
                pq.emplace(d + dist, id);
            }
        }

        for(int i = 1; i <= n; ++i) {
            if(!visited[i]) return -1;
        }

        return ret;
    }
};