UVa 12794 Miss Worm

题目描述

虫小姐住在一个由房间和隧道组成的洞穴中。每条隧道连接两个不同的房间，可以双向通行。洞穴中可能存在环，但每个房间最多属于一个环。隧道和房间很狭窄，虫小姐的身体一旦占据了一条隧道或房间，就不能再次进入。

有些房间有通往地面的出口。虫小姐想知道：对于有地面出口的房间，是否可以从该房间进入洞穴，在洞穴内始终前进（不后退），最后从同一个房间离开，并且走过的路程长度不小于她自身的长度MMM。如果可能，输出最短的可行路程长度；否则输出−1-1−1。

输入格式

输入包含多个测试用例。每个测试用例第一行包含两个整数SSS和TTT（2≤S≤1042 \le S \le 10^42≤S≤104，1≤T≤2S1 \le T \le 2S1≤T≤2S），分别表示房间数和隧道数。房间编号为111到SSS。

接下来TTT行，每行三个整数AAA、BBB和CCC（1≤A<B≤S1 \le A < B \le S1≤A<B≤S，1≤C≤1001 \le C \le 1001≤C≤100），表示一条连接AAA和BBB的隧道，长度为CCC。每个房间连接的隧道数不超过100100100。

接下来一行包含一个整数QQQ（1≤Q≤1001 \le Q \le 1001≤Q≤100），表示查询数量。接下来QQQ行，每行两个整数XXX和MMM（1≤X≤S1 \le X \le S1≤X≤S，1≤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离开。在无向图中，“不后退”意味着不能立即沿着刚刚经过的隧道原路返回，但不禁止绕远路后从另一条路径返回。

由于房间和隧道一旦经过就不能再次进入，虫小姐的行走路径必须是一条简单回路（不重复顶点，起点终点相同）。

回路的结构

在仙人掌图中，任何简单回路必然由以下部分构成：

  1. 从起点XXX出发，沿着树边（或环上的边）走到某个环的入口节点PPP
  2. 从PPP进入该环，完整地绕环一周（因为进入和离开环必须是同一个节点，否则会违反“每个节点最多属于一个环”的约束）
  3. 从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)：

  1. 遍历所有环，只考虑长度≥M\ge M≥M的环
  2. 如果XXX恰好在该环上（即dist[X][c]=0\textit{dist}[X][c] = 0dist[X][c]=0），则可行路程为环的长度
  3. 否则，可行路程为2×dist[X][c] +2 \times \textit{dist}[X][c] \ +2×dist[X][c]+环长
  4. 取所有可行路程中的最小值作为答案；若没有满足条件的环，输出−1-1−1

复杂度分析

  • 找环：O(S+T)O(S + T)O(S+T)
  • 计算距离：对每个环运行一次Dijkstra\texttt{Dijkstra}Dijkstra，环的数量最多为O(S)O(S)O(S)，但由于每个节点最多属于一个环，环的总数不超过S/3S/3S/3。每次Dijkstra\texttt{Dijkstra}Dijkstra的复杂度为O((S+T)log⁡S)O((S + T) \log S)O((S+T)logS)，总复杂度O(S⋅(S+T)log⁡S)O(S \cdot (S + T) \log S)O(S⋅(S+T)logS)在最坏情况下可能较高。实际数据规模下（S≤104S \le 10^4S≤104，T≤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/3，Q≤100Q \le 100Q≤100，完全可行。

代码实现

// Miss Worm// UVa ID: 12794// Verdict: Accepted// Submission Date: 2026-06-13// UVa Run Time: 0.330s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structEdge{intto,w;};intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intS,T;while(cin>>S>>T){vector<vector<Edge>>g(S+1);for(inti=0;i<T;++i){inta,b,c;cin>>a>>b>>c;g[a].push_back({b,c});g[b].push_back({a,c});}// 找环vector<int>parent(S+1,-1),depth(S+1,0),d1(S+1,0);vector<int>cycleId(S+1,-1),cycleLength;vector<bool>visited(S+1,false);function<void(int,int)>dfs=[&](intu,intp){visited[u]=true;for(auto&e:g[u]){intv=e.to;if(v==p)continue;if(visited[v]){if(depth[v]<depth[u]){intcid=cycleLength.size();intw=0;intuu=u;while(uu!=v){cycleId[uu]=cid;w+=d1[uu];uu=parent[uu];}cycleId[v]=cid;w+=e.w;cycleLength.push_back(w);}}else{parent[v]=u;depth[v]=depth[u]+1;d1[v]=e.w;dfs(v,u);}}};for(inti=1;i<=S;++i)if(!visited[i])dfs(i,-1);for(inti=1;i<=S;++i)if(cycleId[i]==-1)cycleId[i]=-2;intnc=cycleLength.size();vector<vector<int>>d2(S+1,vector<int>(nc,-1));for(intcid=0;cid<nc;++cid){priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;vector<bool>done(S+1,false);for(inti=1;i<=S;++i)if(cycleId[i]==cid){d2[i][cid]=0;pq.push(make_pair(0,i));}while(!pq.empty()){pair<int,int>top=pq.top();pq.pop();intd=top.first,u=top.second;if(done[u])continue;done[u]=true;for(size_t j=0;j<g[u].size();++j){Edge&e=g[u][j];intv=e.to,nd=d+e.w;if(d2[v][cid]==-1||nd<d2[v][cid]){d2[v][cid]=nd;pq.push(make_pair(nd,v));}}}}intQ;cin>>Q;while(Q--){intX,M;cin>>X>>M;intr=-1;for(intcid=0;cid<nc;++cid){if(cycleLength[cid]<M)continue;intd=d2[X][cid];if(d==-1)continue;inttotal=(cycleId[X]==cid)?cycleLength[cid]:(2*d+cycleLength[cid]);if(r==-1||total<r)r=total;}cout<<r<<'\n';}}return0;}

总结

本题的核心在于抓住仙人掌图的结构特性：“每个节点最多属于一个环”。基于这一特性，可以推出：

  1. 任何简单回路必须完整地经过某个环（不能只走环的一部分）
  2. 进入和离开环必须是同一个节点
  3. 环的长度必须不小于虫小姐的身体长度

解题步骤可以概括为：

  • 用DFS\texttt{DFS}DFS找出所有环并计算环长
  • 用Dijkstra\texttt{Dijkstra}Dijkstra计算每个节点到每个环的最短距离
  • 对每个查询，在满足长度条件的环中取最优值

关键技巧：将复杂的回路问题转化为“树边往返+++完整环长”的组合，充分利用仙人掌图的特殊性质简化问题。这种分析思路在处理具有特殊约束的图论问题时非常有用。