UVa 627 The Net-洪萨配资

题目描述

给定一个由路由器组成的网络，每个路由器都有一个“路由表”，记录它能直接到达的其他路由器（称为“可见”路由器）。信息在网络中传递时，每经过一个路由器计为一次跳数。需要为若干查询（从源路由器到目标路由器）找到跳数最少的路径。若存在多条跳数相同的路径，则选择字典序最小的路径（即路径上路由器编号序列最小）。若无法到达，则输出相应信息。

输入格式

输入包含多组测试数据。每组数据第一行为一个整数nnn（n≥2n \ge 2n≥2），表示路由器数量。接下来nnn行，每行描述一个路由器的可见列表，格式为：

ID-ID1,ID2,...

接下来一行包含一个整数mmm，表示查询数量。随后mmm行，每行两个整数sss和ttt，表示从路由器sss到路由器ttt的查询。

输入可能包含多组这样的网络描述，直到文件结束。

输出格式

对于每组网络，首先输出一行-----（五个连字符）。然后对于每个查询，输出一行结果：

若存在路径，则输出路径上的路由器编号序列，用空格分隔。
若不存在路径，则输出connection impossible。

样例

输入

6 1-2,3,4 2-1,3 3-1,2,5,6 4-1,5 5-3,4,6 6-3,5 6 1 6 1 5 2 4 2 5 3 6 2 1 10 1-2 2- 3-4 4-8 5-1 6-2 7-3,9 8-10 9-5,6,7 10-8 3 9 10 5 9 9 2

输出

----- 1 3 6 1 3 5 2 1 4 2 3 5 3 6 2 1 ----- 9 7 3 4 8 10 connection impossible 9 6 2

题目分析

本题要求在有向无权图中求两点间的最短路径，且当多条最短路径时输出字典序最小的。由于每个节点可见列表已按升序给出，我们可以利用广度优先搜索（BFS\texttt{BFS}BFS）的特性：BFS\texttt{BFS}BFS按层次扩展，首次到达目标节点的路径一定是跳数最少的。如果我们在BFS\texttt{BFS}BFS过程中按照邻接表升序顺序遍历节点，那么第一次到达目标节点的路径就是字典序最小的最短路径。因为对于同一层，先访问编号较小的节点会优先扩展，从而优先产生字典序较小的路径。

解题思路

构建图：使用map<int, set<int>>存储每个路由器及其可见列表，set自动保持升序。
处理查询：对于每组查询(s,t)(s, t)(s,t)：
- 使用BFS\texttt{BFS}BFS从sss出发，记录每个节点的父节点（即从哪个节点扩展来的）。
- 队列中存储节点，按可见列表升序入队，因此先访问编号较小的节点。
- 当扩展到ttt时，即可停止搜索，因为此时得到的路径是最短且字典序最小的。
- 若ttt未被访问到，则输出connection impossible。
- 否则，通过父节点数组反向回溯得到路径，然后正向输出。
父节点记录：使用map<int, int> parent存储每个节点的前驱，起始节点的父节点设为-1。
输出格式：每组网络前输出一行-----，每组查询结果占一行。

复杂度分析

设节点数为nnn，边数为eee，每个节点可见列表平均长度为ddd。
BFS\texttt{BFS}BFS时间复杂度O(n+e)O(n + e)O(n+e)，空间复杂度O(n)O(n)O(n)。
由于n≤300n \le 300n≤300，d≤50d \le 50d≤50，边数最多150001500015000，完全可接受。

代码实现

// The Net// UVa ID: 627// Verdict: Accepted// Submission Date: 2016-08-28// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,m,start,end;while(cin>>n){cin.ignore(1024,'\n');map<int,set<int>>edges;string line,block;for(inti=1;i<=n;i++){getline(cin,line);inthypen=line.find('-');start=stoi(line.substr(0,hypen));string routers=line.substr(hypen+1);istringstreamiss(routers);while(getline(iss,block,','))edges[start].insert(stoi(block));}cout<<"-----\n";cin>>m;for(intj=1;j<=m;j++){cin>>start>>end;map<int,int>parent;set<int>visited;queue<int>unvisited;unvisited.push(start);parent[start]=-1;visited.insert(start);while(!unvisited.empty()){intcurrent=unvisited.front();unvisited.pop();if(current==end)break;for(autoedge:edges[current])if(visited.find(edge)==visited.end()){parent[edge]=current;visited.insert(edge);unvisited.push(edge);}}if(parent.find(end)==parent.end())cout<<"connection impossible\n";else{vector<int>path;while(parent[end]!=-1){path.insert(path.begin(),end);end=parent[end];}path.insert(path.begin(),end);for(intk=0;k<path.size();k++){if(k>0)cout<<' ';cout<<path[k];}cout<<'\n';}}}return0;}