本文主要是介绍【PAT】1111. Online Map (30)【dijkstra算法】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
Input our current position and a destination, an online map can recommend several paths. Now your job is to recommend two paths to your user: one is the shortest, and the other is the fastest. It is guaranteed that a path exists for any request.
翻译：输入我们当前的位置和目的地，一个在线地图可以推荐几个路径。现在您的任务是向用户推荐两条路径:一条是最短的，另一条是最快的。数据保证任何请求都存在一条路径。
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N (2≤N≤500), and M, being the total number of streets intersections on a map, and the number of streets, respectively. Then M lines follow, each describes a street in the format:
V1 V2 one-way length time
where V1 and V2 are the indices (from 0 to N−1) of the two ends of the street; one-way is 1 if the street is one-way from V1 to V2, or 0 if not; length is the length of the street; and time is the time taken to pass the street.
Finally a pair of source and destination is given.
翻译：每个输入文件包含一组测试数据。对于每组输入数据，第一行包括两个正整数N(2≤N≤500), 和M，分别表示代表地图上道路的交叉点的总数量和道路数量。接下来M行，每行按照以下格式描述一条道路：
V1 V2 one-way length time
V1和V2是道路的两个末端索引(从0到N-1)，one-way如果为1代表是从v1到v2的单行道，0则不是。length代表的是街道的长度；time代表通过这条街道所需的试卷。
最后给出一对起点和终点。
Output Specification:
For each case, first print the shortest path from the source to the destination with distance D in the format:
Distance = D: source -> v1 -> … -> destination
Then in the next line print the fastest path with total time T:
Time = T: source -> w1 -> … -> destination
In case the shortest path is not unique, output the fastest one among the shortest paths, which is guaranteed to be unique. In case the fastest path is not unique, output the one that passes through the fewest intersections, which is guaranteed to be unique.
In case the shortest and the fastest paths are identical, print them in one line in the format:
Distance = D; Time = T: source -> u1 -> … -> destination
翻译：对于每组输入数据，第一行按照以下格式输出从起点到终点的最短路及其长度D：
Distance = D: source -> v1 -> … -> destination
接下来一行输出最快的路及其时间T：
Time = T: source -> w1 -> … -> destination
万一最短路不唯一，输出最短路中最快的那一条，数据保证结果唯一。万一最快的路不唯一，输出经过的交叉点最少的那一条，数据保证结果唯一。
万一最短路和最快的路相同，按照以下格式输出一行：
Distance = D; Time = T: source -> u1 -> … -> destination
Sample Input 1:
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
3 4 0 3 2
3 9 1 4 1
0 6 0 1 1
7 5 1 2 1
8 5 1 2 1
2 3 0 2 2
2 1 1 1 1
1 3 0 3 1
1 4 0 1 1
9 7 1 3 1
5 1 0 5 2
6 5 1 1 2
3 5
Sample Output 1:
Distance = 6: 3 -> 4 -> 8 -> 5
Time = 3: 3 -> 1 -> 5
Sample Input 2:
7 9
0 4 1 1 1
1 6 1 1 3
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 1 3
3 2 1 1 2
4 5 0 2 2
6 5 1 1 2
3 5
Sample Output 2:
Distance = 3; Time = 4: 3 -> 2 -> 5
解题思路
用dijkstra方法搜索两遍即可，注意最短路节点要保存路程和时间，最快路节点要保存时间和经过的节点数，最后判断一下两条路径是否重合。这道题条件比较多，所以有些繁琐，需要仔细思考。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#define INF 99999999
using namespace std;
int N,M;
int d[510][2],Lpre[510],Tpre[510],Lmin,Tmin;
int Lans[510],Tans[510],lcount=1,tcount=1;
int start,destination;
struct Edge{int nodes,time,to;Edge(int a,int b,int c):nodes(a),time(b),to(c){}bool operator<(const Edge tmp)const{if(time==tmp.time) return nodes>tmp.nodes;return time>tmp.time;}
};
struct LengthEdge{int length,time,to;LengthEdge(int a,int b,int c):length(a),time(b),to(c){}bool operator<(const LengthEdge tmp)const{if(length==tmp.length) return time>tmp.time;else return length>tmp.length;}
};
vector<LengthEdge> L[510];void Tdijkstra(int s){priority_queue<Edge> q;for(int i=0;i<N;i++){d[i][0]=d[i][1]=INF;Tpre[i]=-1;}d[s][0]=d[s][1]=0;q.push(Edge(0,0,s));while(!q.empty()){Edge temp=q.top();q.pop();int v=temp.to;if(d[v][0]<temp.time)continue;for(int i=0;i<L[v].size();i++){LengthEdge e=L[v][i];if(d[e.to][0]>d[v][0]+e.time){d[e.to][0]=d[v][0]+e.time;Tpre[e.to]=v;d[e.to][1]=d[v][1]+1;q.push(Edge(d[e.to][1],d[e.to][0],e.to));}else if(d[e.to][0]==d[v][0]+e.time){if(d[e.to][1]>d[v][1]+1){Tpre[e.to]=v;d[e.to][1]=d[v][1]+1;q.push(Edge(d[e.to][1],d[e.to][0],e.to));}}}}Tmin=d[destination][0];
}
void Ldijkstra(int s){priority_queue<LengthEdge> q;for(int i=0;i<N;i++){d[i][0]=d[i][1]=INF;Lpre[i]=-1;}d[s][0]=d[s][1]=0;q.push(LengthEdge(0,0,s));while(!q.empty()){LengthEdge temp=q.top();q.pop();int v=temp.to;if(d[v][0]<temp.length)continue;for(int i=0;i<L[v].size();i++){LengthEdge e=L[v][i];if(d[e.to][0]>d[v][0]+e.length){d[e.to][0]=d[v][0]+e.length;Lpre[e.to]=v;d[e.to][1]=d[v][1]+e.time;q.push(LengthEdge(d[e.to][0],d[e.to][1],e.to));}else if(d[e.to][0]==d[v][0]+e.length){if(d[e.to][1]>d[v][1]+e.time){d[e.to][0]=d[v][0]+e.length;Lpre[e.to]=v;d[e.to][1]=d[v][1]+e.time;q.push(LengthEdge(d[e.to][0],d[e.to][1],e.to));}}}}Lmin=d[destination][0];
}
void LgetPath(){int temp=Lans[0]=destination;lcount=1;while(Lpre[temp]!=-1){Lans[lcount++]=Lpre[temp];temp=Lpre[temp];}
}
void TgetPath(){int temp=Tans[0]=destination;tcount=1;while(Tpre[temp]!=-1){Tans[tcount++]=Tpre[temp];temp=Tpre[temp];}
}
void print(){int i;for(i=0;i<tcount;i++){if(Tans[i]!=Lans[i])break;}if(i==tcount){printf("Distance = %d; Time = %d: %d",Lmin,Tmin,start);for(i=tcount-2;i>=0;i--){printf(" -> %d",Lans[i]);}printf("\n");}else{printf("Distance = %d: %d",Lmin,start);for(i=lcount-2;i>=0;i--){printf(" -> %d",Lans[i]);}printf("\n");printf("Time = %d: %d",Tmin,start);for(i=tcount-2;i>=0;i--){printf(" -> %d",Tans[i]);}printf("\n"); }
}
int main(){scanf("%d%d",&N,&M);int a,b,c,d,e;for(int i=0;i<M;i++){scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);L[a].push_back(LengthEdge(d,e,b));if(c!=1){L[b].push_back(LengthEdge(d,e,a));}}scanf("%d%d",&start,&destination);Ldijkstra(start);Tdijkstra(start);LgetPath();TgetPath();print();return 0;
}这篇关于【PAT】1111. Online Map (30)【dijkstra算法】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
