题干给你一个整数n表示图中的节点数量这些节点按从0到n - 1编号。同时给你一个长度为n的整数数组nums以及一个整数maxDiff。如果满足|nums[i] - nums[j]| maxDiff即nums[i]和nums[j]的绝对差至多为maxDiff则节点i和节点j之间存在一条无向边。此外给你一个二维整数数组queries。对于每个queries[i] [ui, vi]找到节点ui和节点vi之间的最短距离。如果两节点之间不存在路径则返回-1。返回一个数组answer其中answer[i]是第i个查询的结果。注意节点之间的边是无权重unweighted的。示例 1输入n 5, nums [1,8,3,4,2], maxDiff 3, queries [[0,3],[2,4]]输出[1,1]解释生成的图如下查询最短路径最短距离[0, 3]0 → 31[2, 4]2 → 41因此输出为 [1, 1]。示例 2输入n 5, nums [5,3,1,9,10], maxDiff 2, queries [[0,1],[0,2],[2,3],[4,3]]输出[1,2,-1,1]解释生成的图如下查询最短路径最短距离[0, 1]0 → 11[0, 2]0 → 1 → 22[2, 3]无-1[4, 3]3 → 41因此输出为 [1, 2, -1, 1]。示例 3输入n 3, nums [3,6,1], maxDiff 1, queries [[0,0],[0,1],[1,2]]输出[0,-1,-1]解释由于以下原因任意两个节点之间都不存在边节点 0 和节点 1|3 - 6| 3 1节点 0 和节点 2|3 - 1| 2 1节点 1 和节点 2|6 - 1| 5 1因此不存在任何可以到达其他节点的路径输出为 [0, -1, -1]。提示1 n nums.length 10^50 nums[i] 10^50 maxDiff 10^51 queries.length 10^5queries[i] [ui, vi]0 ui, vi n苯人思路动态规划递归#includebits/stdc.husingnamespacestd;classSolution{public:// 递归函数// 根据已知的边 (i, next)遍历包含节点 next 的所有边另一节点为 j更新 dp[i][j] 和 RecordSet[i]、RecordSet[j]voidrecur(vectorvectorintRecordSet,vectorvectorintdp){intnRecordSet.size();intflag0;// 判断递归是否该结束的变量vectorvectorinttemRecordSet;// 复制 RecordSet 临时使用防止引用失效报错for(inti0;in;i){for(autonext:RecordSet[i]){for(autoj:RecordSet[next]){if(ji)continue;if(dp[i][j]0){dp[i][j]dp[i][next]dp[next][j];dp[j][i]dp[i][next]dp[next][j];tem[i].emplace_back(j);tem[j].emplace_back(i);flag;// 若在该次递归中进行了操作则flag不为0需要继续递归continue;}elseif(dp[i][j]dp[i][next]dp[next][j]){dp[i][j]dp[i][next]dp[next][j];dp[j][i]dp[i][next]dp[next][j];flag;}}}}// RecordSet.clear();RecordSettem;if(flag0)recur(RecordSet,dp);}vectorintpathExistenceQueries(intn,vectorintnums,intmaxDiff,vectorvectorintqueries){vectorvectorintdp(n,vectorint(n,0));// dp[i][j]表示i到j的最短距离// 类似题目 3532. 针对图的路径存在性查询Ⅰ// 创建索引数组并按 nums 值排序便于后面与 maxDiff 的比较与处理vectorintcomp(n,0);iota(comp.begin(),comp.end(),0);sort(comp.begin(),comp.end(),[](inta,intb){returnnums[a]nums[b];});// RecordSet[i] 记录与节点 i 形成了有向边的所有节点 j 的值vectorvectorintRecordSet(n);for(inti0;in-1;i){for(intji1;jn;j){if(nums[comp[j]]-nums[comp[i]]maxDiff)break;dp[comp[i]][comp[j]]1;dp[comp[j]][comp[i]]1;RecordSet[comp[i]].emplace_back(comp[j]);RecordSet[comp[j]].emplace_back(comp[i]);}}recur(RecordSet,dp);for(inti0;in;i){for(intj0;jn;j){if(dp[i][j]0i!j){dp[i][j]-1;dp[j][i]-1;}}}vectorintanswer;for(autoquestion:queries){answer.emplace_back(dp[question[0]][question[1]]);}returnanswer;}};该方法会超时通过 619/682于是增加了 visit 来记录每次递归后改变的最短边包含的节点使下一次递归时能遍历更少的节点和边但仍然超时。遂需要彻底改变思路以下是 AC 的代码。AC 代码classSolution{public:vectorintpathExistenceQueries(intn,vectorintnums,intmaxDiff,vectorvectorintqueries){// 1. 排序vectorintcomp(n);iota(comp.begin(),comp.end(),0);sort(comp.begin(),comp.end(),[](inta,intb){returnnums[a]nums[b];});vectorintsorted_nums(n);for(inti0;in;i){sorted_nums[i]nums[comp[i]];}// 2. 位置映射// nums 中位置为 comp[i] 的数从小到大排序后位于位置 i// pos 将 节点编号 映射到 排序后的位置vectorintpos(n);for(inti0;in;i){pos[comp[i]]i;}// 3. 计算每个位置向右最远能到达的位置vectorintright_most(n);intr0;for(inti0;in;i){if(ri)ri;while(r1nsorted_nums[r1]-sorted_nums[i]maxDiff){r;}right_most[i]r;}// 4. 倍增预处理constintLOG17;vectorvectorintjump(LOG,vectorint(n));for(inti0;in;i){jump[0][i]right_most[i];// jump[0][i] 表示从位置 i 出发跳 1 次能到达的最远位置}for(intk1;kLOG;k){for(inti0;in;i){jump[k][i]jump[k-1][jump[k-1][i]];// jump[k][i] 表示从位置 i 出发跳 2^k 次能到达的最远位置// 核心思想跳 2^k 次 先跳 2^(k-1) 次再跳 2^(k-1) 次}}// 5. 处理查询vectorintanswer;answer.reserve(queries.size());// 预分配空间避免多次扩容for(autoq:queries){intuq[0],vq[1];// 如果起点和终点相同最短距离为 0不需要移动if(uv){answer.push_back(0);continue;}intpupos[u],pvpos[v];// 转换为排序后的位置if(pupv)swap(pu,pv);// 保证 pu pv即从左向右跳因为图是无向的反向查询等价于正向查询// 直接可达if(right_most[pu]pv){answer.push_back(1);continue;}// 倍增求最小步数// 用最少的跳跃次数从 pu 接近 pv但永远不超过 pvintsteps0;intcurpu;// 当前位置// 贪心策略// - 从最大的步长开始尝试// - 如果跳 2^k 次后仍然到不了 pv即 jump[k][cur] pv就跳过去// - 这样可以最大化每次跳跃的进度同时保证不跳过目标for(intkLOG-1;k0;k--){if(jump[k][cur]pv){curjump[k][cur];steps(1k);}}// 再跳一次到达 pvif(jump[0][cur]pv){answer.push_back(steps1);}else{answer.push_back(-1);}}returnanswer;}};
3534. 针对图的路径存在性查询 II（2026.07.10）
题干给你一个整数n表示图中的节点数量这些节点按从0到n - 1编号。同时给你一个长度为n的整数数组nums以及一个整数maxDiff。如果满足|nums[i] - nums[j]| maxDiff即nums[i]和nums[j]的绝对差至多为maxDiff则节点i和节点j之间存在一条无向边。此外给你一个二维整数数组queries。对于每个queries[i] [ui, vi]找到节点ui和节点vi之间的最短距离。如果两节点之间不存在路径则返回-1。返回一个数组answer其中answer[i]是第i个查询的结果。注意节点之间的边是无权重unweighted的。示例 1输入n 5, nums [1,8,3,4,2], maxDiff 3, queries [[0,3],[2,4]]输出[1,1]解释生成的图如下查询最短路径最短距离[0, 3]0 → 31[2, 4]2 → 41因此输出为 [1, 1]。示例 2输入n 5, nums [5,3,1,9,10], maxDiff 2, queries [[0,1],[0,2],[2,3],[4,3]]输出[1,2,-1,1]解释生成的图如下查询最短路径最短距离[0, 1]0 → 11[0, 2]0 → 1 → 22[2, 3]无-1[4, 3]3 → 41因此输出为 [1, 2, -1, 1]。示例 3输入n 3, nums [3,6,1], maxDiff 1, queries [[0,0],[0,1],[1,2]]输出[0,-1,-1]解释由于以下原因任意两个节点之间都不存在边节点 0 和节点 1|3 - 6| 3 1节点 0 和节点 2|3 - 1| 2 1节点 1 和节点 2|6 - 1| 5 1因此不存在任何可以到达其他节点的路径输出为 [0, -1, -1]。提示1 n nums.length 10^50 nums[i] 10^50 maxDiff 10^51 queries.length 10^5queries[i] [ui, vi]0 ui, vi n苯人思路动态规划递归#includebits/stdc.husingnamespacestd;classSolution{public:// 递归函数// 根据已知的边 (i, next)遍历包含节点 next 的所有边另一节点为 j更新 dp[i][j] 和 RecordSet[i]、RecordSet[j]voidrecur(vectorvectorintRecordSet,vectorvectorintdp){intnRecordSet.size();intflag0;// 判断递归是否该结束的变量vectorvectorinttemRecordSet;// 复制 RecordSet 临时使用防止引用失效报错for(inti0;in;i){for(autonext:RecordSet[i]){for(autoj:RecordSet[next]){if(ji)continue;if(dp[i][j]0){dp[i][j]dp[i][next]dp[next][j];dp[j][i]dp[i][next]dp[next][j];tem[i].emplace_back(j);tem[j].emplace_back(i);flag;// 若在该次递归中进行了操作则flag不为0需要继续递归continue;}elseif(dp[i][j]dp[i][next]dp[next][j]){dp[i][j]dp[i][next]dp[next][j];dp[j][i]dp[i][next]dp[next][j];flag;}}}}// RecordSet.clear();RecordSettem;if(flag0)recur(RecordSet,dp);}vectorintpathExistenceQueries(intn,vectorintnums,intmaxDiff,vectorvectorintqueries){vectorvectorintdp(n,vectorint(n,0));// dp[i][j]表示i到j的最短距离// 类似题目 3532. 针对图的路径存在性查询Ⅰ// 创建索引数组并按 nums 值排序便于后面与 maxDiff 的比较与处理vectorintcomp(n,0);iota(comp.begin(),comp.end(),0);sort(comp.begin(),comp.end(),[](inta,intb){returnnums[a]nums[b];});// RecordSet[i] 记录与节点 i 形成了有向边的所有节点 j 的值vectorvectorintRecordSet(n);for(inti0;in-1;i){for(intji1;jn;j){if(nums[comp[j]]-nums[comp[i]]maxDiff)break;dp[comp[i]][comp[j]]1;dp[comp[j]][comp[i]]1;RecordSet[comp[i]].emplace_back(comp[j]);RecordSet[comp[j]].emplace_back(comp[i]);}}recur(RecordSet,dp);for(inti0;in;i){for(intj0;jn;j){if(dp[i][j]0i!j){dp[i][j]-1;dp[j][i]-1;}}}vectorintanswer;for(autoquestion:queries){answer.emplace_back(dp[question[0]][question[1]]);}returnanswer;}};该方法会超时通过 619/682于是增加了 visit 来记录每次递归后改变的最短边包含的节点使下一次递归时能遍历更少的节点和边但仍然超时。遂需要彻底改变思路以下是 AC 的代码。AC 代码classSolution{public:vectorintpathExistenceQueries(intn,vectorintnums,intmaxDiff,vectorvectorintqueries){// 1. 排序vectorintcomp(n);iota(comp.begin(),comp.end(),0);sort(comp.begin(),comp.end(),[](inta,intb){returnnums[a]nums[b];});vectorintsorted_nums(n);for(inti0;in;i){sorted_nums[i]nums[comp[i]];}// 2. 位置映射// nums 中位置为 comp[i] 的数从小到大排序后位于位置 i// pos 将 节点编号 映射到 排序后的位置vectorintpos(n);for(inti0;in;i){pos[comp[i]]i;}// 3. 计算每个位置向右最远能到达的位置vectorintright_most(n);intr0;for(inti0;in;i){if(ri)ri;while(r1nsorted_nums[r1]-sorted_nums[i]maxDiff){r;}right_most[i]r;}// 4. 倍增预处理constintLOG17;vectorvectorintjump(LOG,vectorint(n));for(inti0;in;i){jump[0][i]right_most[i];// jump[0][i] 表示从位置 i 出发跳 1 次能到达的最远位置}for(intk1;kLOG;k){for(inti0;in;i){jump[k][i]jump[k-1][jump[k-1][i]];// jump[k][i] 表示从位置 i 出发跳 2^k 次能到达的最远位置// 核心思想跳 2^k 次 先跳 2^(k-1) 次再跳 2^(k-1) 次}}// 5. 处理查询vectorintanswer;answer.reserve(queries.size());// 预分配空间避免多次扩容for(autoq:queries){intuq[0],vq[1];// 如果起点和终点相同最短距离为 0不需要移动if(uv){answer.push_back(0);continue;}intpupos[u],pvpos[v];// 转换为排序后的位置if(pupv)swap(pu,pv);// 保证 pu pv即从左向右跳因为图是无向的反向查询等价于正向查询// 直接可达if(right_most[pu]pv){answer.push_back(1);continue;}// 倍增求最小步数// 用最少的跳跃次数从 pu 接近 pv但永远不超过 pvintsteps0;intcurpu;// 当前位置// 贪心策略// - 从最大的步长开始尝试// - 如果跳 2^k 次后仍然到不了 pv即 jump[k][cur] pv就跳过去// - 这样可以最大化每次跳跃的进度同时保证不跳过目标for(intkLOG-1;k0;k--){if(jump[k][cur]pv){curjump[k][cur];steps(1k);}}// 再跳一次到达 pvif(jump[0][cur]pv){answer.push_back(steps1);}else{answer.push_back(-1);}}returnanswer;}};
