题目描述给定一个无向图节点为城市由两位大写字母标识每条边的长度均为111。对于每个查询给定起点和终点城市要求输出一条最短路径若存在多条输出任意一条即可路径以边的序列形式表示每行一条边格式为“城市 城市”。若不存在路径则输出No route。输入包含多个测试用例每个测试用例以边数nnn开始随后nnn行描述边最后一行给出查询的起点和终点。不同测试用例之间由空行分隔输出也需用空行分隔。输入格式输入包含多个测试用例。每个测试用例的第一行为一个整数nnn表示边的数量。接下来nnn行每行两个由两个大写字母组成的字符串表示一条无向边的两个端点。随后一行两个字符串表示查询的起点和终点。输入直至文件结束。输出格式对于每个测试用例若存在路径则输出最短路径上的每条边每行一条格式为“城市 城市”两个城市代码间用一个空格分隔。若不存在路径输出No route。不同测试用例的输出之间用一个空行分隔。样例输入3 JV PT KA PT KA HP JV HP 2 JV PT KA HP JV HP样例输出JV PT PT KA No route题目分析该问题为无向无权图上的单源最短路径问题边权均为111因此使用广度优先搜索BFS\texttt{BFS}BFS可在O(VE)O(VE)O(VE)时间内求出从起点到所有点的最短路径。由于只需要输出任意一条最短路径可在BFS\texttt{BFS}BFS过程中记录每个节点的前驱节点最后从终点回溯至起点输出路径上的每条边。若终点未被访问则说明不存在路径。城市代码由两个大写字母组成共有26×2667626 \times 26 67626×26676个可能的城市可以直接将城市编码为整数例如(first - A) * 26 (second - A)以简化存储和访问。图使用邻接表存储。解题思路实现步骤确定如下步骤1\texttt{1}1. 对于每个测试用例读入边数nnn。初始化邻接表edges大小为676676676清空所有边。步骤2\texttt{2}2. 读入nnn条边每条边包含两个城市字符串from和to将其转换为整数索引并在邻接表中相互添加边无向图。步骤3\texttt{3}3. 读入查询的起点source和终点dest转换为整数索引s和t。步骤4\texttt{4}4. 若s t则直接输出该城市和自身的边即source dest。否则执行BFS\texttt{BFS}BFS初始化距离数组dist为−1-1−1前驱数组parent为−1-1−1访问标记visited为false。将s入队dist[s] 0visited[s] true。当队列非空取出队首节点u遍历其所有邻接节点v。若v未被访问则设置visited[v] truedist[v] dist[u] 1parent[v] u并将v入队。步骤5\texttt{5}5.BFS\texttt{BFS}BFS结束后若dist[t] -1则无路径输出No route否则使用递归或迭代从t回溯到s按顺序输出每条边。递归函数print_path(u, v)中若parent[v] ! u则递归调用print_path(u, parent[v])然后输出边parent[v] -- v否则直接输出边u -- v。步骤6\texttt{6}6. 每个测试用例输出后若还有后续用例输出一个空行。由于城市总数固定邻接表大小固定为676676676BFS\texttt{BFS}BFS的时间复杂度为O(676E)O(676 E)O(676E)完全满足要求。代码实现// We Ship Cheap// UVa ID: 762// Verdict: Accepted// Submission Date: 2016-11-30// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAX_V700;intparent[MAX_V],visited[MAX_V],dist[MAX_V];vectorintedges[MAX_V];intget_indexer(stringname){return(name.front()-A)*26(name.back()-A);}stringget_name(intindexer){string name;name(char)(indexer/26A);name(char)(indexer%26A);returnname;}// 广度优先遍历。voidbfs(intu){memset(parent,-1,sizeof(parent));memset(visited,0,sizeof(visited));memset(dist,-1,sizeof(dist));// 存储未访问顶点的队列将起始顶点放入队列中。queueintunvisited;unvisited.push(u);visited[u]true;dist[u]0;// 当队列不为空时继续处理。while(!unvisited.empty()){// 取出尚未访问的顶点intvunvisited.front();unvisited.pop();// 遍历与当前顶点相连接的其他顶点如果其他顶点未发现则将其加入到队列中// 并将后继顶点的父顶点设置为当前顶点。for(autonext:edges[v])if(!visited[next]){unvisited.push(next);visited[next]1,parent[next]v,dist[next]dist[v]1;}}}// 使用递归输出路径。voidfind_path(intu,intv){if(parent[v]!u){find_path(u,parent[v]);coutget_name(parent[v]) get_name(v)\n;}elsecoutget_name(u) get_name(v)\n;;}intmain(intargc,char*argv[]){// 读入图数据。intn,cases0;while(cinn){if(cases0)cout\n;intcounter0;for(inti0;iMAX_V;i)edges[i].clear();string from,to;intstart,end;for(inti1;in;i){cinfromto;startget_indexer(from),endget_indexer(to);edges[start].push_back(end);edges[end].push_back(start);}cinfromto;if(fromto)coutfrom to\n;else{// 使用广度优先遍历从第一个顶点开始遍历图。startget_indexer(from),endget_indexer(to);bfs(start);if(dist[end]!-1)find_path(start,end);elsecoutNo route\n;}}return0;}总结本题通过BFS\texttt{BFS}BFS在无权图上求最短路径并利用前驱数组回溯输出路径。城市编码为整数简化了图的存储使得算法与具体城市名称无关。BFS\texttt{BFS}BFS保证找到的路径最短且任意一条最短路径均可接受。注意输入输出格式中空行的处理使用cases变量在每组之间输出空行。该解法时间复杂度O(VE)O(VE)O(VE)空间复杂度O(VE)O(VE)O(VE)对于V≤676V \le 676V≤676极其高效。