1724. Checking Existence of Edge Length Limited Paths II

An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes, and the graph may not be connected.

Implement the DistanceLimitedPathsExist class:

• DistanceLimitedPathsExist(int n, int[][] edgeList) Initializes the class with an undirected graph.
• boolean query(int p, int q, int limit) Returns true if there exists a path from p to q such that each edge on the path has a distance strictly less than limit, and otherwise false.

c++

class DistanceLimitedPathsExist {
    map<int, vector<int>> ufmp;
    
    int find(vector<int>& uf, int n) {
        return uf[n] == n ? n : uf[n] = find(uf, uf[n]);
    }
    void uni(vector<int>& uf, int u, int v) {
        int pu = find(uf,u), pv = find(uf,v);
        uf[pu] = uf[pv] = min(pu,pv);
    }
public:
    DistanceLimitedPathsExist(int n, vector<vector<int>>& edgeList) {
        priority_queue<array<int,3>,vector<array<int,3>>, greater<array<int,3>>> pq;
        vector<int> uf(n);
        for(int i = 0; i < n; i++) uf[i] = i;
        for(auto e : edgeList) {
            pq.push({e[2],e[0],e[1]});
        }
        while(!pq.empty()) {
            int tc = pq.top()[0];
            while(!pq.empty() and pq.top()[0] == tc) {
                auto [c, u, v] = pq.top(); pq.pop();
                uni(uf,u,v);
            }
            ufmp[tc] = uf;
        }
    }
    
    bool query(int p, int q, int limit) {
        auto it = ufmp.lower_bound(limit);
        if(it == begin(ufmp)) return false;
        --it;
        return find(it->second, p) == find(it->second, q);
    }
};

/**
 * Your DistanceLimitedPathsExist object will be instantiated and called as such:
 * DistanceLimitedPathsExist* obj = new DistanceLimitedPathsExist(n, edgeList);
 * bool param_1 = obj->query(p,q,limit);
 */