743. Network Delay Time

    int networkDelayTime(vector<vector<int>>& times, int N, int K) {
        int dmax = 1e7;
        vector<bool> used(N+1, false);
        vector<int> d(N+1, dmax);
        vector<vector<pair<int,int>>> u2v(N+1);
        for(int i=0; i<times.size(); i++) {
            u2v[times[i][0]].push_back({times[i][1], times[i][2]});
        }
        queue<int> q;
        q.push(K);
        d[K] = 0;
        while(!q.empty()) {
            int u = q.front();
            q.pop();
// make current node available because signal delay may be smaller through a different path that has not been counted
            used[u] = false;
            for(auto &p: u2v[u]){
                int v = p.first, w = p.second;
                int dv = d[u] + w;
                if(dv < d[v]) {
                    d[v] = dv;
                    if(!used[v]) {
                        q.push(v);
                        used[v] = true;
                    }
                }
            }   
        }
        int res = 0;
        for(int i=1; i<N+1; i++) {
            if(d[i]>=dmax) return -1;
            res = max(res, d[i]);
        }
        return res;
    }