题目描述银河系中有nnn颗行星上有人类定居点编号从000到n−1n-1n−1。每个行星都有一个超空间跳跃门理论上允许从任意行星UUU到任意其他行星VVV的跳跃。但由于技术原因并非所有n(n−1)n(n-1)n(n−1)种跳跃都是允许的某些从UUU到VVV的跳跃被禁止。题目以区间形式给出禁止跳跃每行输入格式为U V1−V2U \ V1 - V2UV1−V2表示从行星UUU到行星V1,V11,…,V2V1, V11, \ldots, V2V1,V11,…,V2包含两端的所有跳跃是被禁止的。要求计算从起点SSS到终点TTT所需的最少跳跃次数如果不可达则输出Impossible\texttt{Impossible}Impossible。题目分析问题本质这是一个无权图上的最短路径问题节点nnn个行星编号0…n−10 \ldots n-10…n−1。边理论上所有有序对(u,v)(u, v)(u,v)u≠vu \neq vuv都是允许的但题目给出了某些从uuu到连续区间[V1,V2][V1, V2][V1,V2]的跳跃是被禁止的。因此允许的边就是除了这些禁止边之外的所有边。目标求从SSS到TTT的最少步数。数据规模n≤100,000n \leq 100,000n≤100,000k≤41,000k \leq 41,000k≤41,000禁止区间的数量禁止跳跃的总对数≤5,000,000\leq 5,000,000≤5,000,000难点分析图非常稠密理论上完全图有约n2n^2n2条边无法显式存储。禁止边数量可能很大虽然kkk不大但每个禁止区间可能覆盖大量节点总禁止边数可达5×1065 \times 10^65×106。需要快速找到可到达的节点在 BFS 中从当前节点uuu出发需要知道哪些vvv是可以到达且未被访问过的。关键观察由于允许的边几乎就是全集除了禁止区间我们可以换个角度思考维护一个集合unvisited\texttt{unvisited}unvisited存放所有尚未被访问过的节点。当访问节点uuu时我们想找到所有可以到达的vvv即未被禁止且未被访问。因为允许的边是除了禁止区间外的所有边所以这些vvv就是unvisited\texttt{unvisited}unvisited集合中除去禁止区间后剩余的所有节点。这样BFS 的过程就变成了从unvisited\texttt{unvisited}unvisited中取出所有可以到达的节点将它们加入队列并从unvisited\texttt{unvisited}unvisited中删除。问题转化为如何高效地从有序集合中批量删除多个区间内的元素。解题思路数据结构选择禁止区间存储使用vectorvectorpairint, int forbidden(n)\texttt{vectorvectorpairint, int forbidden(n)}vectorvectorpairint, int forbidden(n)对于每个节点uuu存储它的所有禁止区间[l,r][l, r][l,r]。未访问节点集合使用setint unvisited\texttt{setint unvisited}setint unvisited支持有序遍历和删除操作。BFS 队列标准队列存储(节点,距离)(节点, 距离)(节点,距离)。算法步骤初始化将所有节点0…n−10 \ldots n-10…n−1插入unvisited\texttt{unvisited}unvisited集合。起点处理将SSS从unvisited\texttt{unvisited}unvisited中删除加入队列距离为000。BFS\texttt{BFS}BFS循环取出队首节点uuu和当前距离distdistdist。如果uTu TuT返回distdistdist。获取uuu的所有禁止区间列表ban\texttt{ban}ban。遍历unvisited\texttt{unvisited}unvisited集合跳过所有落在禁止区间内的节点将剩余的节点收集到toVisit\texttt{toVisit}toVisit列表中。对于toVisit\texttt{toVisit}toVisit中的每个节点vvv从unvisited\texttt{unvisited}unvisited中删除vvv。将(v,dist1)(v, dist1)(v,dist1)加入队列。结束如果队列为空仍未找到TTT返回Impossible\texttt{Impossible}Impossible。关键技巧在遍历unvisited\texttt{unvisited}unvisited集合时我们需要高效地跳过多个禁止区间。做法如下使用迭代器it\texttt{it}it指向当前遍历位置。对每个禁止区间[l,r][l, r][l,r]找到第一个≥l\geq l≥l的节点位置在此之前的所有节点都是可到达的加入toVisit\texttt{toVisit}toVisit。将迭代器移动到第一个r rr的位置即跳过整个禁止区间。处理完所有禁止区间后将剩余的所有节点也加入toVisit\texttt{toVisit}toVisit。这样每个节点只会被访问一次加入toVisit\texttt{toVisit}toVisit一次总复杂度为O((nO((n O((n禁止区间总数)log⁡n)) \log n))logn)可以接受。复杂度分析时间复杂度O((n∑∣banu∣)log⁡n)O((n \sum |ban_u|) \log n)O((n∑∣banu​∣)logn)其中∑∣banu∣≤k\sum |ban_u| \leq k∑∣banu​∣≤k最坏情况下约O((nk)log⁡n)O((n k) \log n)O((nk)logn)。空间复杂度O(nk)O(n k)O(nk)用于存储禁止区间和未访问集合。代码实现// Galactic Travel// UVa ID: 11165// Verdict: Accepted// Submission Date: 2026-02-25// UVa Run Time: 0.080s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intsolve(intn,intk,vectorvectorpairint,intforbidden,intS,intT){// 初始化未访问集合setintunvisited;for(inti0;in;i)unvisited.insert(i);// BFS 队列queuepairint,intq;// (node, dist)q.push({S,0});unvisited.erase(S);while(!q.empty()){intuq.front().first;intdistq.front().second;q.pop();if(uT)returndist;// 获取当前节点 u 的禁止区间列表autobanforbidden[u];vectorinttoVisit;// 遍历 unvisited 集合跳过禁止区间autoitunvisited.begin();for(autointerval:ban){intlinterval.first,rinterval.second;// 找到第一个 l 的节点autoendItunvisited.upper_bound(r);// 收集 [it, 第一个禁止节点) 区间内的节点while(it!unvisited.end()*itl){toVisit.push_back(*it);it;}// 跳过整个禁止区间 [l, r]itendIt;}// 收集剩余的节点while(it!unvisited.end()){toVisit.push_back(*it);it;}// 将这些节点加入队列并从 unvisited 中删除for(intv:toVisit){unvisited.erase(v);q.push({v,dist1});}}return-1;// 不可达}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;cinN;for(intcaseNum1;caseNumN;caseNum){intn,k;cinnk;// 禁止区间列表forbidden[u] 存储 u 的所有禁止区间 [l, r]vectorvectorpairint,intforbidden(n);for(inti0;ik;i){intu,v1,v2;chardash;cinuv1dashv2;// 格式 U V1-V2forbidden[u].emplace_back(v1,v2);}intS,T;cinST;intanssolve(n,k,forbidden,S,T);coutCase #caseNum: ;if(ans-1)coutImpossible\n;elsecoutans\n;}return0;}总结本题的核心思想是利用集合维护未访问节点通过跳过禁止区间来快速找到可到达节点。这种方法避免了显式建图充分利用了允许边近乎全集的特性在稠密图中也能高效运行。对于类似的大规模图上BFS\texttt{BFS}BFS问题如果允许边远多于禁止边这种逆向思维非常有用。