力扣 1697. 检查边长度限制的路径是否存在_limitj

给你一个 n 个点组成的无向图边集 edgeList ，其中 edgeList[i] = [ui, vi, disi] 表示点 ui 和点 vi 之间有一条长度为 disi 的边。请注意，两个点之间可能有 超过一条边 。

给你一个查询数组queries ，其中 queries[j] = [pj, qj, limitj] ，你的任务是对于每个查询 queries[j] ，判断是否存在从 pj 到 qj 的路径，且这条路径上的每一条边都 严格小于 limitj 。

请你返回一个 布尔数组 answer ，其中 answer.length == queries.length ，当 queries[j] 的查询结果为 true 时， answer 第 j 个值为 true ，否则为 false 。

示例 1：

 

输入：n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
输出：[false,true]
解释：上图为给定的输入数据。注意到 0 和 1 之间有两条重边，分别为 2 和 16 。
对于第一个查询，0 和 1 之间没有小于 2 的边，所以我们返回 false 。
对于第二个查询，有一条路径（0 -> 1 -> 2）两条边都小于 5 ，所以这个查询我们返回 true 。

示例 2：

 

输入：n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
输出：[true,false]
解释：上图为给定数据。

提示：

    2 <= n <= 105
    1 <= edgeList.length, queries.length <= 105
    edgeList[i].length == 3
    queries[j].length == 3
    0 <= ui, vi, pj, qj <= n - 1
    ui != vi
    pj != qj
    1 <= disi, limitj <= 109
    两个点之间可能有 多条 边。

思路：

首先要想到，要么是每次查询是log的，要么就是预处理答案，然后O1查询。
这里显然是不会O1查询的。
然后考虑到两点间的最大值是不是小于limit，是就true。
因为我们是要构造一颗最小生成树，即先合并边权小的边。
那么我们可以遍历询问，对询问以limit为关键字从小到大排序。
合并边权小于limit的，判断一下两个询问的点是不是在集合内即可。
如果不在，说明这两点是不会联通的或者两点间的边权会有大于limit的情况

代码：

class Solution {
public:
    int f[1<<17];
    int find(int x){
        return f[x]==x?x:f[x]=find(f[x]);
    }
    struct node{
        int s,t,limit;
        int id;
    }a[1<<17];
    struct N{
        int s,t,v;
    }b[1<<17];
    static bool cmp1(node &a,node &b){
        return a.limit<b.limit;
    }
    static bool cmp2(N &a,N &b){
        return a.v<b.v;
    }
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& ed, vector<vector<int>>& q) {
        for(int i=0;i<1<<17;i++) f[i]=i;
        vector<bool> ans;
        ans.resize(q.size());
        for(int i=0;i<q.size();i++){
                a[i]={q[i][0],q[i][1],q[i][2],i};
        }
        for(int i=0;i<ed.size();i++){
            b[i]={ed[i][0],ed[i][1],ed[i][2]};
        }
        sort(a,a+q.size(),cmp1);
        sort(b,b+ed.size(),cmp2);
        int j=0;
        for(int i=0;i<q.size();i++){
            while(j<ed.size() && a[i].limit>b[j].v){
                f[find(b[j].s)]=find(b[j].t);
                j++;
            }
            ans[a[i].id]= find(a[i].s)==find(a[i].t);
        }
        return ans;
    }
};