当前位置：首页 > news >正文

UVa 11165 Galactic Travel

news 2026/4/14 21:06:04

题目描述

银河系中有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,V1+1,…,V2V1, V1+1, \ldots, V2V1,V1+1,…,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,000
k≤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中删除。
问题转化为：如何高效地从有序集合中批量删除多个区间内的元素。

解题思路

数据结构选择

禁止区间存储：使用vector<vector<pair<int, int>>> forbidden(n)\texttt{vector<vector<pair<int, int>>> forbidden(n)}vector<vector<pair<int, int>>> forbidden(n)，对于每个节点uuu，存储它的所有禁止区间[l,r][l, r][l,r]。
未访问节点集合：使用set<int> unvisited\texttt{set<int> unvisited}set<int> 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。
- 如果u==Tu == Tu==T，返回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,dist+1)(v, dist+1)(v,dist+1)加入队列。
结束：如果队列为空仍未找到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> r>r的位置，即跳过整个禁止区间。
处理完所有禁止区间后，将剩余的所有节点也加入toVisit\texttt{toVisit}toVisit。

这样，每个节点只会被访问一次（加入toVisit\texttt{toVisit}toVisit一次），总复杂度为O((n+O((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((n+k)log⁡n)O((n + k) \log n)O((n+k)logn)。
空间复杂度：O(n+k)O(n + k)O(n+k)用于存储禁止区间和未访问集合。

代码实现

// Galactic Travel// UVa ID: 11165// Verdict: Accepted// Submission Date: 2026-02-25// UVa Run Time: 0.080s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intsolve(intn,intk,vector<vector<pair<int,int>>>&forbidden,intS,intT){// 初始化未访问集合set<int>unvisited;for(inti=0;i<n;++i)unvisited.insert(i);// BFS 队列queue<pair<int,int>>q;// (node, dist)q.push({S,0});unvisited.erase(S);while(!q.empty()){intu=q.front().first;intdist=q.front().second;q.pop();if(u==T)returndist;// 获取当前节点 u 的禁止区间列表auto&ban=forbidden[u];vector<int>toVisit;// 遍历 unvisited 集合，跳过禁止区间autoit=unvisited.begin();for(auto&interval:ban){intl=interval.first,r=interval.second;// 找到第一个 >= l 的节点autoendIt=unvisited.upper_bound(r);// 收集 [it, 第一个禁止节点) 区间内的节点while(it!=unvisited.end()&&*it<l){toVisit.push_back(*it);++it;}// 跳过整个禁止区间 [l, r]it=endIt;}// 收集剩余的节点while(it!=unvisited.end()){toVisit.push_back(*it);++it;}// 将这些节点加入队列并从 unvisited 中删除for(intv:toVisit){unvisited.erase(v);q.push({v,dist+1});}}return-1;// 不可达}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;cin>>N;for(intcaseNum=1;caseNum<=N;++caseNum){intn,k;cin>>n>>k;// 禁止区间列表，forbidden[u] 存储 u 的所有禁止区间 [l, r]vector<vector<pair<int,int>>>forbidden(n);for(inti=0;i<k;++i){intu,v1,v2;chardash;cin>>u>>v1>>dash>>v2;// 格式 "U V1-V2"forbidden[u].emplace_back(v1,v2);}intS,T;cin>>S>>T;intans=solve(n,k,forbidden,S,T);cout<<"Case #"<<caseNum<<": ";if(ans==-1)cout<<"Impossible\n";elsecout<<ans<<"\n";}return0;}