7-2 天梯地图 （30 分）
本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。
输入格式：
输入在第一行给出两个正整数N（2 ≤ N ≤ 500）和M，分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行，每行按如下格式给出一条道路的信息：
V1 V2 one-way length time
其中V1和V2是道路的两个端点的编号（从0到N-1）；如果该道路是从V1到V2的单行线，则one-way为1，否则为0；length是道路的长度；time是通过该路所需要的时间。最后给出一对起点和终点的编号。
输出格式：
首先按下列格式输出最快到达的时间T和用节点编号表示的路线：
Time = T: 起点 => 节点1 => ... => 终点
然后在下一行按下列格式输出最短距离D和用节点编号表示的路线：
Distance = D: 起点 => 节点1 => ... => 终点
如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。
如果这两条路线是完全一样的，则按下列格式输出：
Time = T; Distance = D: 起点 => 节点1 => ... => 终点
输入样例1：
10 15
0 1 0 1 1
8 0 0 1 1
4 8 1 1 1
5 4 0 2 3
5 9 1 1 4
0 6 0 1 1
7 3 1 1 2
8 3 1 1 2
2 5 0 2 2
2 1 1 1 1
1 5 0 1 3
1 4 0 1 1
9 7 1 1 3
3 1 0 2 5
6 3 1 2 1
5 3
输出样例1：
Time = 6: 5 => 4 => 8 => 3
Distance = 3: 5 => 1 => 3
输入样例2：
7 9
0 4 1 1 1
1 6 1 3 1
2 6 1 1 1
2 5 1 2 2
3 0 0 1 1
3 1 1 3 1
3 2 1 2 1
4 5 0 2 2
6 5 1 2 1
3 5
输出样例2：
Time = 3; Distance = 4: 3 => 2 => 5
#include<stdio.h> #include<iostream> using namespace std; int sum[521];//记录找最短时间时到原点的距离 struct { int length; int time; }Graph[521][521];//建立地图 struct { int visit; int length; int pre; }LVisit[521];//建立距离、访问表 struct { int visit; int time; int pre; }TVisit[521];//建立时间、访问表 void InitGraph(int N, int M)//创建并初始化地图 { for(int i=0; i<=N; i++)//初始化各点间的距离和时间均为无穷大 for(int j=0; j<=N; j++){ sum[j] = 0; Graph[i][j].length = 9999999; Graph[i][j].time = 9999999; } int v1, v2, way, length, time; for(int i=0; i<M; i++){//读取输入创建地图 cin>>v1>>v2>>way>>length>>time; Graph[v1][v2].length = length; Graph[v1][v2].time = time; if(way == 0){//非单行线，两地可互通 Graph[v2][v1].length = length; Graph[v2][v1].time = time; } } } void InitVisit(int N, int S)// 初始化时间、距离、访问表 { for(int i=0; i<=N; i++){ LVisit[i].visit = 0;//初始化为未访问 LVisit[i].length = Graph[S][i].length;//根据地图初始化到原点距离 TVisit[i].visit = 0;//初始化为未访问 TVisit[i].time = Graph[S][i].time;//根据地图初始化时间 if(TVisit[i].time!=9999999){//如果和原点相通设置前驱点为原点，并设置个时间点到原点距离 LVisit[i].pre = S; TVisit[i].pre = S; sum[i] = Graph[S][i].length; } } LVisit[S].visit = 1;//设置原点已访问 TVisit[S].visit = 1;//设置原点已访问 } void DST_L(int N, int S)//斯特拉求最短距离 { for(int j=1; j<N; j++){ int mlpoint = N;//设置N点为最近点，N点已设为无穷远 for(int i=0; i<N; i++){ if(LVisit[i].length<LVisit[mlpoint].length&&!LVisit[i].visit) mlpoint = i; }//求出最近点并设置为已访问 LVisit[mlpoint].visit = 1; for(int i=0; i<N; i++){//更新距离 if(!LVisit[i].visit){ //更新为更短的距离 if(LVisit[i].length>LVisit[mlpoint].length+Graph[mlpoint][i].length){ LVisit[i].length = LVisit[mlpoint].length+Graph[mlpoint][i].length; LVisit[i].pre = mlpoint;//设置前驱点 } //距离相同则节点少为优 else if(LVisit[i].length==LVisit[mlpoint].length+Graph[mlpoint][i].length){ int l1=0,l2=0; int pre = LVisit[i].pre; while(pre!=S){ l1++; pre = LVisit[pre].pre; } pre = mlpoint; while(pre!=S){ l2++; pre = LVisit[pre].pre; } if(l1>l2)//节点多则更新 LVisit[i].pre = mlpoint; } } } } } void DST_T(int N, int S)//斯特拉求最短时间 { for(int j=1; j<N; j++){ int mtpoint = N;//无穷为最短点 for(int i=0; i<N; i++){ if(TVisit[i].time<TVisit[mtpoint].time&&!TVisit[i].visit) mtpoint = i; }//求出最短点并设置为已访问 TVisit[mtpoint].visit = 1; for(int i=0; i<N; i++){ if(!TVisit[i].visit){ //更新最短时间 if(TVisit[i].time>TVisit[mtpoint].time+Graph[mtpoint][i].time){ TVisit[i].time = TVisit[mtpoint].time+Graph[mtpoint][i].time; TVisit[i].pre = mtpoint; sum[i] = sum[mtpoint] + Graph[mtpoint][i].length;//更新最短时间的距离 }//时间相同则根据距离更新，距离短的优先 else if(TVisit[i].time==TVisit[mtpoint].time+Graph[mtpoint][i].time){ if(sum[i]>sum[mtpoint]+Graph[mtpoint][i].length){//选距离更短的 TVisit[i].pre = mtpoint; sum[i] = sum[mtpoint] + Graph[mtpoint][i].length;//更新其距离 } } } } } } int main() { int N, M; cin>>N>>M; InitGraph(N,M);//初始化并读取输入创建图 int S, D; cin>>S>>D; InitVisit(N, S);//创建并初始化距离、时间、访问表 DST_L(N,S);//求最短距离 DST_T(N,S);//求最短时间 int lpath[521];//最短距离路径表 int tpath[521];//最短时间路径表 int l=520, t=520;; int pre = D; while(pre!=S){//根据目的地不断往后后移，直到后移到原点 lpath[l]=pre; pre = LVisit[pre].pre; l--; } pre = D; while(pre!=S){ tpath[t] = pre; pre = TVisit[pre].pre; t--; } if(t==l){//路径长度一样 int flag = 0; for(int i=t+1; i<521; i++){//判断路径是否完全相同 if(tpath[i]!=lpath[i]) flag = 1;//不相等 } if(flag == 1){//路径不同 cout<<"Time = "<<TVisit[D].time<<": "<<S; for(int i = t+1; i<521; i++){ cout<<" => "<<tpath[i]; } cout<<endl; cout<<"Distance = "<<LVisit[D].length<<": "<<S; for(int i = l+1; i<521; i++){ cout<<" => "<<lpath[i]; } } else{//路径相同 cout<<"Time = "<<TVisit[D].time<<"; "<<"Distance = "<<LVisit[D].length<<": "<<S; for(int i = t+1; i<521; i++){ cout<<" => "<<tpath[i]; } } return 0; } //路径不同 cout<<"Time = "<<TVisit[D].time<<": "<<S; for(int i = t+1; i<521; i++){ cout<<" => "<<tpath[i]; } cout<<endl; cout<<"Distance = "<<LVisit[D].length<<": "<<S; for(int i = l+1; i<521; i++){ cout<<" => "<<lpath[i]; } }