（Dijkstra）7-13 天梯地图（30 分)

电玩女神 2022-02-27 20:50 130阅读 0赞

本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。

### 输入格式： ###

输入在第一行给出两个正整数`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<iostream>
    #include<cstdio>
    #include<cstring>
    #include<stack>
    using namespace std;
    const int INF=0x3f3f3f3f;
    const int maxn=510;
    int n,m,mp[maxn][maxn],time1[maxn][maxn],dist[maxn],tm[maxn],dt[maxn],cnt[maxn];
    int vis[maxn],p1[maxn],p2[maxn];
    
    void Dijkstra(int s,int t){
    	memset(vis,0,sizeof(vis));
    	memset(cnt,INF,sizeof(cnt));
    	for(int i=0;i<n;i++){
    		dist[i]=mp[s][i];
    		p1[i]=s;
    	}
    	p1[s]=-1;
    	cnt[s]=1;
    	vis[s]=1;
    	
    	for(int i=1;i<n;i++){
    		int tmp=INF,k;	
    		for(int j=0;j<n;j++){
    			if(!vis[j]&&tmp>dist[j]){
    				tmp=dist[j];
    				k=j;
    			}
    		}
    		if(k==t||tmp==INF) return ;
    		vis[k]=1;
    		for(int j=0;j<n;j++){
    			if(!vis[j]){
    				if(dist[j]>dist[k]+mp[k][j]){
    					dist[j]=dist[k]+mp[k][j];
    					cnt[j]=cnt[k]+1;
    					p1[j]=k;
    				}else if(dist[j]==dist[k]+mp[k][j]&&cnt[j]>cnt[k]+1){
    					cnt[j]=cnt[k]+1;
    					p1[j]=k;
    				}
    			}
    		}
    	}
    }
    
    void Dijkstra1(int s,int t){
    	memset(vis,0,sizeof(vis));
    	for(int i=0;i<n;i++){
    		tm[i]=time1[s][i];
    		dt[i]=mp[s][i];
    		p2[i]=s;
    	}
    	vis[s]=1;
    	p2[s]=-1;
    	
    	for(int i=1;i<n;i++){
    		int tmp=INF,k;
    		for(int j=0;j<n;j++){
    			if(!vis[j]&&tmp>tm[j]){
    				tmp=tm[j];
    				k=j;
    			}
    		}
    		if(k==t||tmp==INF) return ;
    		vis[k]=1;
    		for(int j=0;j<n;j++){
    			if(!vis[j]){
    				if(tm[j]>tm[k]+time1[k][j]){
    					tm[j]=tm[k]+time1[k][j];
    					dt[j]=dt[k]+mp[k][j];
    					p2[j]=k;
    				}else if(tm[j]==tm[k]+time1[k][j]&&dt[j]>dt[k]+mp[k][j]){
    					dt[j]=dt[k]+mp[k][j];
    					p2[j]=k;
    				}
    			}
    		}
    	}
    }
    
    
    void init(){
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			if(i==j){
    				mp[i][j]=time1[i][j]=0;
    			}else{
    				mp[i][j]=time1[i][j]=INF;
    			} 
    		}
    	}
    }
    
    void printTrace(int t){
    	//printf("t=%d\n",t);
    	stack<int> q1;
    	stack<int> q2;
    	int x=t;
    	while(x!=-1){
    		q1.push(x);
    		//printf("x=%d,****A\n",x);
    		x=p1[x];
    	}
    	
    	x=t;
    	while(x!=-1){
    		q2.push(x);
    		x=p2[x];
    	}
    	
    	bool flag;
    	if(q1==q2){
    		printf("Time = %d; Distance = %d:",tm[t],dist[t]);
    		flag=false;
    		while(!q1.empty()){
    			x=q1.top();
    			q1.pop();
    			if(!flag){
    				flag=true;
    				printf(" %d",x);
    			}else{
    				printf(" => %d",x);
    			}
    		}
    		printf("\n");
    	}else{
    		printf("Time = %d:",tm[t]);
    		flag=false;
    		while(!q2.empty()){
    			x=q2.top();
    			q2.pop();
    			if(!flag){
    				flag=true;
    				printf(" %d",x);
    			}else{
    				printf(" => %d",x);
    			}
    		}
    		printf("\n");
    		
    		printf("Distance = %d:",dist[t]);
    		flag=false;
    		while(!q1.empty()){
    			x=q1.top();
    			q1.pop();
    			if(!flag){
    				flag=true;
    				printf(" %d",x);
    			}else{
    				printf(" => %d",x);
    			}
    		}
    		printf("\n");
    	}
    	
    }
    
    int main(){
    	scanf("%d%d",&n,&m);
    	init();
    	int u,v,f,d,s,t;
    	for(int i=0;i<m;i++){
    		scanf("%d%d%d%d%d",&u,&v,&f,&d,&t);
    		mp[u][v]=min(mp[u][v],d);
    		time1[u][v]=min(time1[u][v],t);
    		if(f==0){
    			mp[v][u]=min(mp[v][u],d);
    			time1[v][u]=min(time1[v][u],t);
    		}
    	}
    	scanf("%d%d",&s,&t);
    	
    	Dijkstra(s,t);
    	Dijkstra1(s,t);
    	printTrace(t);
    	return 0;
    }