L3-007 天梯地图（30 分) 最短路 dijkstra

野性酷女 2022-02-28 13:38 179阅读 0赞

L3-007 天梯地图 （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

跑两遍dj~

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<sstream>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int ma[505][505];//存路径长度 
    int tim[505][505];//存路径时间 
    int point[505],vis[505]; //存结点数和访问标记 
    int dis[505],dit[505];//存最短路径、最短时间 
    int pretim[505],predis[505];//存前驱 
    int main()
    {
    	int n,m,s,e,i,j;
    	int x,y,k,t,l;
    	vector<int> v1,v2;//存输出 
    	memset(pretim,-1,sizeof pretim);
    	memset(predis,-1,sizeof predis);
    	memset(tim,inf,sizeof tim);
    	memset(ma,inf,sizeof ma);
    	memset(dis,inf,sizeof dis);
    	memset(dit,inf,sizeof dit);
    	scanf("%d%d",&n,&m);
    	for(i=0;i<m;i++)
    	{
    		scanf("%d%d%d%d%d",&x,&y,&k,&l,&t);
    		ma[x][y]=l;
    		tim[x][y]=t;
    		if(k==0)
    		{
    			ma[y][x]=l;
    			tim[y][x]=t;
    		}
    	}
    	scanf("%d%d",&s,&e);
    	//time	
    	dit[s]=0;
    	dis[s]=0;
    	vis[s]=1;
    	for(i=0;i<n;i++)
    	{
    		int mi=s,maxi=inf;
    		for(j=0;j<n;j++)
    		{
    			if(vis[j]==0&&dit[j]<maxi)
    			{
    				maxi=dit[j];
    				mi=j;
    			}
    		}
    		vis[mi]=1;
    		for(j=0;j<n;j++)
    		{
    			if(vis[j]==0)
    			{
    				if(dit[j]>dit[mi]+tim[mi][j])
    				{
    					dit[j]=dit[mi]+tim[mi][j];
    					dis[j]=dis[mi]+ma[mi][j];
    					pretim[j]=mi;
    				}
    				else if(dit[j]==dit[mi]+tim[mi][j])
    				{
    					if(dis[j]>dis[mi]+ma[mi][j])
    					{
    						dis[j]=dis[mi]+ma[mi][j];
    						pretim[j]=mi;
    					}
    				}
    			}
    		}
    	}
    	int TIME=dit[e];
    	//distance
    	memset(point,0,sizeof point);
    	memset(vis,0,sizeof vis);
    	memset(dis,inf,sizeof dis);
    	memset(dit,inf,sizeof dit);
    	dit[s]=0;
    	dis[s]=0;
    	vis[s]=1;
    	for(i=0;i<n;i++)
    	{
    		int mi=s,maxi=inf;
    		for(j=0;j<n;j++)
    		{
    			if(vis[j]==0&&dis[j]<maxi)
    			{
    				maxi=dis[j];
    				mi=j;
    			}
    		}
    		vis[mi]=1;
    		for(j=0;j<n;j++)
    		{
    			if(vis[j]==0)
    			{
    				if(dis[j]>dis[mi]+ma[mi][j])
    				{
    					dis[j]=dis[mi]+ma[mi][j];
    					point[j]=point[mi]+1;
    					predis[j]=mi;
    				}
    				else if(dis[j]==dis[mi]+ma[mi][j])
    				{
    					if(point[j]>point[mi]+1)
    					{
    						point[j]=point[mi]+1;
    						predis[j]=mi;
    					}
    				}
    			}
    		}
    	}
    	y=e;
    	while(y!=-1)
    	{
    		v1.push_back(y);
    		y=pretim[y];
    	}
    	y=e;
    	while(y!=-1)
    	{
    		v2.push_back(y);
    		y=predis[y];
    	}
    	reverse(v1.begin(),v1.end());
    	reverse(v2.begin(),v2.end());
    	int f=1;
    	if(v1.size()==v2.size())
    	{
    		f=2;
    		for(i=0;i<v1.size();i++)
    		{
    			if(v1[i]!=v2[i])f=1;
    		}
    		if(f==2)
    		f=0;
    	}
    	if(f)
    	{
    		printf("Time = %d: %d",TIME,s);
    		for(i=1;i<v1.size();i++)
    			printf(" => %d",v1[i]);
    		printf("\nDistance = %d: %d",dis[e],s);
    		for(i=1;i<v2.size();i++)
    			printf(" => %d",v2[i]);
    	}
    	else
    	{
    		printf("Time = %d; Distance = %d: %d",TIME,dis[e],s);
    		for(i=1;i<v1.size();i++)
    		printf(" => %d",v1[i]);
    		printf("\n");
    	}
    	
    }