UVa 627 The Net

题目描述给定一个由路由器组成的网络每个路由器都有一个“路由表”记录它能直接到达的其他路由器称为“可见”路由器。信息在网络中传递时每经过一个路由器计为一次跳数。需要为若干查询从源路由器到目标路由器找到跳数最少的路径。若存在多条跳数相同的路径则选择字典序最小的路径即路径上路由器编号序列最小。若无法到达则输出相应信息。输入格式输入包含多组测试数据。每组数据第一行为一个整数nnnn≥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过程中按照邻接表升序顺序遍历节点那么第一次到达目标节点的路径就是字典序最小的最短路径。因为对于同一层先访问编号较小的节点会优先扩展从而优先产生字典序较小的路径。解题思路构建图使用mapint, setint存储每个路由器及其可见列表set自动保持升序。处理查询对于每组查询(s,t)(s, t)(s,t)使用BFS\texttt{BFS}BFS从sss出发记录每个节点的父节点即从哪个节点扩展来的。队列中存储节点按可见列表升序入队因此先访问编号较小的节点。当扩展到ttt时即可停止搜索因为此时得到的路径是最短且字典序最小的。若ttt未被访问到则输出connection impossible。否则通过父节点数组反向回溯得到路径然后正向输出。父节点记录使用mapint, int parent存储每个节点的前驱起始节点的父节点设为-1。输出格式每组网络前输出一行-----每组查询结果占一行。复杂度分析设节点数为nnn边数为eee每个节点可见列表平均长度为ddd。BFS\texttt{BFS}BFS时间复杂度O(ne)O(n e)O(ne)空间复杂度O(n)O(n)O(n)。由于n≤300n \le 300n≤300d≤50d \le 50d≤50边数最多150001500015000完全可接受。代码实现// The Net// UVa ID: 627// Verdict: Accepted// Submission Date: 2016-08-28// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intn,m,start,end;while(cinn){cin.ignore(1024,\n);mapint,setintedges;string line,block;for(inti1;in;i){getline(cin,line);inthypenline.find(-);startstoi(line.substr(0,hypen));string routersline.substr(hypen1);istringstreamiss(routers);while(getline(iss,block,,))edges[start].insert(stoi(block));}cout-----\n;cinm;for(intj1;jm;j){cinstartend;mapint,intparent;setintvisited;queueintunvisited;unvisited.push(start);parent[start]-1;visited.insert(start);while(!unvisited.empty()){intcurrentunvisited.front();unvisited.pop();if(currentend)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())coutconnection impossible\n;else{vectorintpath;while(parent[end]!-1){path.insert(path.begin(),end);endparent[end];}path.insert(path.begin(),end);for(intk0;kpath.size();k){if(k0)cout ;coutpath[k];}cout\n;}}}return0;}总结本题通过BFS\texttt{BFS}BFS求最短路径并利用邻接表升序存储和BFS\texttt{BFS}BFS的层次遍历特性保证了在跳数相同时输出字典序最小的路径。关键在于理解BFS\texttt{BFS}BFS的性质和字典序比较的规则。代码实现简洁高效适用于中等规模的网络。