UVa 12794 Miss Worm

题目描述虫小姐住在一个由房间和隧道组成的洞穴中。每条隧道连接两个不同的房间可以双向通行。洞穴中可能存在环但每个房间最多属于一个环。隧道和房间很狭窄虫小姐的身体一旦占据了一条隧道或房间就不能再次进入。有些房间有通往地面的出口。虫小姐想知道对于有地面出口的房间是否可以从该房间进入洞穴在洞穴内始终前进不后退最后从同一个房间离开并且走过的路程长度不小于她自身的长度MMM。如果可能输出最短的可行路程长度否则输出−1-1−1。输入格式输入包含多个测试用例。每个测试用例第一行包含两个整数SSS和TTT2≤S≤1042 \le S \le 10^42≤S≤1041≤T≤2S1 \le T \le 2S1≤T≤2S分别表示房间数和隧道数。房间编号为111到SSS。接下来TTT行每行三个整数AAA、BBB和CCC1≤AB≤S1 \le A B \le S1≤AB≤S1≤C≤1001 \le C \le 1001≤C≤100表示一条连接AAA和BBB的隧道长度为CCC。每个房间连接的隧道数不超过100100100。接下来一行包含一个整数QQQ1≤Q≤1001 \le Q \le 1001≤Q≤100表示查询数量。接下来QQQ行每行两个整数XXX和MMM1≤X≤S1 \le X \le S1≤X≤S1≤M≤1051 \le M \le 10^51≤M≤105表示入口房间和虫小姐的身体长度。输入以文件结束符终止。输出格式对于每个查询输出一行一个整数最短可行路程长度若不可能输出−1-1−1。样例输入4 4 1 2 12 2 3 10 3 4 8 2 4 5 3 1 23 4 10 1 24 8 9 1 2 1 2 3 1 3 4 1 2 5 10 5 6 25 2 6 20 3 7 9 7 8 3 3 8 4 4 1 10 4 60 8 5 7 55输出47 23 -1 20 -1 16 71题目分析图结构特点题目给出了一个关键约束每个房间最多属于一个环。这意味着整个洞穴是一个仙人掌图cactus graph\texttt{cactus graph}cactus graph每个连通分量要么是一棵树要么是一个环加上若干以环上节点为根的树。行走规则分析虫小姐需要从入口XXX进入始终前进不后退最后从XXX离开。在无向图中“不后退”意味着不能立即沿着刚刚经过的隧道原路返回但不禁止绕远路后从另一条路径返回。由于房间和隧道一旦经过就不能再次进入虫小姐的行走路径必须是一条简单回路不重复顶点起点终点相同。回路的结构在仙人掌图中任何简单回路必然由以下部分构成从起点XXX出发沿着树边或环上的边走到某个环的入口节点PPP从PPP进入该环完整地绕环一周因为进入和离开环必须是同一个节点否则会违反“每个节点最多属于一个环”的约束从PPP沿着原路返回XXX关键推论环的长度必须不小于虫小姐的身体长度MMM。因为虫小姐需要将自己的整个身体完全放入洞穴中而环是唯一的连续回路身体无法跨越环与树的交接处而不违反“不重复进入”的规则。特殊情况如果XXX本身就在某个环上那么XXX可以直接作为入口点PPP此时往返距离为000总路程即为该环的长度。如果XXX不在任何环上则必须走到某个环的入口节点再返回。解题思路第一步找出所有环使用深度优先搜索DFS\texttt{DFS}DFS遍历图。维护每个节点的父节点、深度和到父节点的距离。当遇到一条指向已访问节点且不是父节点的边时就找到了一个环。从当前节点沿着父链向上回溯到该祖先节点即可收集环上的所有节点并计算环的长度。由于每个节点最多属于一个环这种找环方法是正确且高效的。第二步计算节点到环的距离对于每个环以环上的所有节点作为源点运行单源最短路径算法Dijkstra\texttt{Dijkstra}Dijkstra计算出图中所有节点到该环的最短距离。由于边权最大为100100100也可以使用BFS\texttt{BFS}BFS加优先队列但Dijkstra\texttt{Dijkstra}Dijkstra是最通用的选择。设dist[X][c]\textit{dist}[X][c]dist[X][c]表示节点XXX到第ccc个环的最短距离。第三步处理查询对于每个查询(X,M)(X, M)(X,M)遍历所有环只考虑长度≥M\ge M≥M的环如果XXX恰好在该环上即dist[X][c]0\textit{dist}[X][c] 0dist[X][c]0则可行路程为环的长度否则可行路程为2×dist[X][c] 2 \times \textit{dist}[X][c] \ 2×dist[X][c]环长取所有可行路程中的最小值作为答案若没有满足条件的环输出−1-1−1复杂度分析找环O(ST)O(S T)O(ST)计算距离对每个环运行一次Dijkstra\texttt{Dijkstra}Dijkstra环的数量最多为O(S)O(S)O(S)但由于每个节点最多属于一个环环的总数不超过S/3S/3S/3。每次Dijkstra\texttt{Dijkstra}Dijkstra的复杂度为O((ST)log⁡S)O((S T) \log S)O((ST)logS)总复杂度O(S⋅(ST)log⁡S)O(S \cdot (S T) \log S)O(S⋅(ST)logS)在最坏情况下可能较高。实际数据规模下S≤104S \le 10^4S≤104T≤2ST \le 2ST≤2S环数较少这种方法可以接受。另一种优化是使用BFS\texttt{BFS}BFS加双端队列处理单位边权边权为111但本题边权为111到100100100故使用Dijkstra\texttt{Dijkstra}Dijkstra。查询每个查询O(环数)O(\text{环数})O(环数)环数≤S/3\le S/3≤S/3Q≤100Q \le 100Q≤100完全可行。代码实现// Miss Worm// UVa ID: 12794// Verdict: Accepted// Submission Date: 2026-06-13// UVa Run Time: 0.330s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structEdge{intto,w;};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intS,T;while(cinST){vectorvectorEdgeg(S1);for(inti0;iT;i){inta,b,c;cinabc;g[a].push_back({b,c});g[b].push_back({a,c});}// 找环vectorintparent(S1,-1),depth(S1,0),d1(S1,0);vectorintcycleId(S1,-1),cycleLength;vectorboolvisited(S1,false);functionvoid(int,int)dfs[](intu,intp){visited[u]true;for(autoe:g[u]){intve.to;if(vp)continue;if(visited[v]){if(depth[v]depth[u]){intcidcycleLength.size();intw0;intuuu;while(uu!v){cycleId[uu]cid;wd1[uu];uuparent[uu];}cycleId[v]cid;we.w;cycleLength.push_back(w);}}else{parent[v]u;depth[v]depth[u]1;d1[v]e.w;dfs(v,u);}}};for(inti1;iS;i)if(!visited[i])dfs(i,-1);for(inti1;iS;i)if(cycleId[i]-1)cycleId[i]-2;intnccycleLength.size();vectorvectorintd2(S1,vectorint(nc,-1));for(intcid0;cidnc;cid){priority_queuepairint,int,vectorpairint,int,greaterpairint,intpq;vectorbooldone(S1,false);for(inti1;iS;i)if(cycleId[i]cid){d2[i][cid]0;pq.push(make_pair(0,i));}while(!pq.empty()){pairint,inttoppq.top();pq.pop();intdtop.first,utop.second;if(done[u])continue;done[u]true;for(size_t j0;jg[u].size();j){Edgeeg[u][j];intve.to,ndde.w;if(d2[v][cid]-1||ndd2[v][cid]){d2[v][cid]nd;pq.push(make_pair(nd,v));}}}}intQ;cinQ;while(Q--){intX,M;cinXM;intr-1;for(intcid0;cidnc;cid){if(cycleLength[cid]M)continue;intdd2[X][cid];if(d-1)continue;inttotal(cycleId[X]cid)?cycleLength[cid]:(2*dcycleLength[cid]);if(r-1||totalr)rtotal;}coutr\n;}}return0;}总结本题的核心在于抓住仙人掌图的结构特性“每个节点最多属于一个环”。基于这一特性可以推出任何简单回路必须完整地经过某个环不能只走环的一部分进入和离开环必须是同一个节点环的长度必须不小于虫小姐的身体长度解题步骤可以概括为用DFS\texttt{DFS}DFS找出所有环并计算环长用Dijkstra\texttt{Dijkstra}Dijkstra计算每个节点到每个环的最短距离对每个查询在满足长度条件的环中取最优值关键技巧将复杂的回路问题转化为“树边往返完整环长”的组合充分利用仙人掌图的特殊性质简化问题。这种分析思路在处理具有特殊约束的图论问题时非常有用。