743. Network Delay Time

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

• Time : O(t + nlogt)
• Space : O(n)

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        unordered_map<int, vector<pair<int,int>>> g;
        vector<int> visit(n,-1);
        for(auto& t : times) {
            g[t[0]-1].push_back({t[1]-1,t[2]});
        }
        visit[k-1] = 0;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.push({0,k-1});
        while(!pq.empty()) {
            auto [time, id] = pq.top(); pq.pop();
            if(visit[id] != time) continue;
            for(auto [next, cost] : g[id]) {
                if(visit[next] == -1 or visit[next] > time + cost) {
                    visit[next] = time + cost;
                    pq.push({time + cost, next});
                }
            }
        }

        int res = 0;
        for(auto delay : visit) {
            if(delay == -1) return -1;
            res = max(res, delay);
        }
        return res;
    }
};