UVa 341 Non-Stop Travel

题目描述David\texttt{David}David讨厌在开车时遇到停车标志、让行标志和交通信号灯。为了最大限度地减少这种烦恼他准备了常去区域的交通地图并测量了每个路口的平均延误时间以秒为单位。他想找到指定起点和终点之间能够最小化路口延误的路线无论为了避开延误需要行驶多远距离并请求你的帮助。输入格式对于每个区域David\texttt{David}David提供一张地图。地图数据首先给出路口数量NININI不超过101010个。路口从111开始顺序编号。对于每个路口输入指定从该路口出发的街道数量然后对于每条街道输入目标路口编号和该路口的平均延误时间。在最后一个路口的数据之后输入起点和终点的路口编号。整个输入由一系列地图组成最后跟一个单独的整数000。注意每条街道是单向的。要表示双向街道需要包含两个方向的记录。从III到JJJ最多只有一条街道。每个区域中最小平均延误的路线是唯一的。输出格式对于每个区域按顺序输出一行包含区域编号、路线经过的路口序列以及总延误时间。格式如样例所示。样例输入5 2 3 3 4 6 3 1 2 3 7 5 6 1 4 5 0 1 4 7 2 4 2 1 2 5 1 1 6 1 2 7 4 2 5 3 13 4 8 5 18 2 3 7 6 14 1 6 6 2 3 5 5 9 3 6 2 7 9 4 6 1 7 2 0 1 7 0样例输出Case 1: Path 2 1 4; 8 second delay Case 2: Path 1 2 3 6 7; 20 second delay题目分析问题的本质这是一个单源最短路径问题。给定一个有向图每个顶点路口有经过时的延误边权需要找到从起点到终点的最短路径总延误最小。关键点顶点数≤10\leq 10≤10图很小每条边有权重延误时间需要输出路径图是有向图与经典最短路径的区别这里延误与路口关联而不是与道路关联。但从输入格式看延误是在街道数据中给出的实际上是到达目标路口时的延误。因此可以将其视为边权。算法选择由于图很小可以使用Dijkstra\texttt{Dijkstra}Dijkstra算法O(N2)O(N^2)O(N2)实现N≤10N \leq 10N≤10简单高效Bellman-Ford\texttt{Bellman-Ford}Bellman-Ford算法Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法全源最短路径路径记录在更新距离的同时记录每个节点的前驱节点parent[v]最终从终点回溯到起点即可得到路径。参考代码// Non-Stop Travel// UVa ID: 341// Verdict: Accepted// Submission Date: 2016-06-28// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structedge{intindex,delay;// 目标路口编号延误时间};// 递归输出路径voidfindPath(intparent[],intend,intstart){if(end!start)findPath(parent,parent[end],start);cout end;}intmain(intargc,char*argv[]){intn,cases0;while(cinn,n){// 构建邻接表vectorvectoredgeedges(n1);for(inti1;in;i){intpairs;cinpairs;for(intj1;jpairs;j){intnext,delay;cinnextdelay;edges[i].push_back((edge){next,delay});}}// 读取起点和终点intstart,end;cinstartend;// Dijkstra 算法数据结构intdistances[n1],parent[n1],visited[n1];fill(distances,distancesn1,-1);// -1 表示不可达fill(parent,parentn1,-1);fill(visited,visitedn1,0);distances[start]0;intcurrentstart;while(visited[current]0){visited[current]1;// 松弛当前节点的所有出边for(inti0;iedges[current].size();i){edge eedges[current][i];if(visited[e.index]0){if(distances[e.index]-1||distances[current]e.delaydistances[e.index]){distances[e.index]distances[current]e.delay;parent[e.index]current;}}}// 选择未访问的距离最小的节点intminDistance-1;for(inti1;in;i)if(visited[i]0){if(distances[i]0(minDistance-1||distances[i]minDistance)){minDistancedistances[i];currenti;}}}// 输出结果coutCase cases: Path ;findPath(parent,end,start);cout; distances[end] second delayendl;}return0;}