检查边长度限制的路径是否存在

题目

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

---

给你一个 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 <= 10^5
• 1 <= edgeList.length, queries.length <= 10^5
• edgeList[i].length == 3
• queries[j].length == 3
• 0 <= ui, vi, pj, qj <= n - 1
• ui != vi
• pj != qj
• 1 <= disi, limitj <= 10^9
• 两个点之间可能有 多条 边。

题解

思路

离线操作，将查询的limit按照升序排序。将所有边按照边权升序排序。

接下来用双指针，在遍历查询时将小于当前limit的所有边都纳入到同一个集合。然后检查当前所查询的两个点是否在同一集合即可。

代码

class Solution {
public:
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        int st[n]; memset(st, -1, sizeof(st));
        function<int(int)> ufind = [&](int x) {
            return st[x]<0?x:st[x] = ufind(st[x]);
        };

        sort(edgeList.begin(), edgeList.end(), [](auto& x, auto& y) {
            return x[2] < y[2];
        });
        int esz = edgeList.size(), qsz = queries.size();
        vector<int> id(qsz);
        vector<bool> ans(qsz);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int x,int y) {
            return queries[x][2] < queries[y][2];
        });
        int p = 0;
        for (int i:id) {
            auto& q = queries[i];
            while (p<esz && edgeList[p][2] < q[2]) {
                int x = ufind(edgeList[p][0]), y = ufind(edgeList[p][1]);
                if (x != y) {
                    st[x] = y;
                }
                p++;
            }
            ans[i] = (ufind(q[0]) == ufind(q[1]));
        }
        return ans;
    }
};