最短时间（最短路+思维）

题目描述

梦工厂有 n 个分厂（从 1 开始编号），有m对分厂通过双向铁路相连。
为了保证每两个分厂之间的同学可以方便地进行交流，掌舵人张老师就在那些没有铁路连接的分厂之间建造了公路。
在两个直接通过公路或铁路相连的分厂之间移动，需要花费 1 小时。
现在菜鸡wxy和hbz都从1厂出发，wxy开火车，hbz开汽车，各自前往n厂。但是，他们中途不能同时停在同一个分厂
（但是可以同时停在n厂）。
现在请你来为wxy和hbz分别设计一条线路，使他们尽可能快地到达n厂（即要求他们中最后到达n厂的时间最短）。
所有的公路或铁路可以被多次使用，求最短时间。(火车和汽车可以同时到达n，也可以先后到达。)

输入

首先有 2 个整数 n 和 m (2<=n<=500, 0<=m<=n*（n-1)/2 分别表示梦工厂分厂的数目和铁路的数目；

接下来的 m 对数字，每对由两个整数 u 和 v 构成，表示小镇 u 和小镇 v 之间有一条铁路。(u!=v  1<=u,v<=n)
输入保证无重边

输出

输出一个整数，表示答案，如果没有合法的路线规划，输出-1

样例输入

4 3
1 2
2 3
3 4

样例输出

3

思路：如果修的铁路有1-n的就可以铁路就可以1小时到达，公路跑最短路，公路是没修铁路的地方，遍历一下，找出公路跑最短路，如果没有1-n的铁路，公路可以1小时到达，铁路跑最短路

代码：
 

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#define INF 0x3f3f3f3f

using namespace std;


bool vis[505];

int dis[505];
int n,m;
void Dijkstra(int map[505][505])
{
	for(int t=1;t<=n;t++)
	{
		dis[t]=INF;
		vis[t]=false;
	}
	dis[1]=0;
	for(int t=1;t<=n;t++)
	{
		int min=INF;
		int k=-1;
		for(int j=1;j<=n;j++)
		{
			if(vis[j]==false&&dis[j]<min)
			{
				min=dis[j];
				k=j;
			}
		}
		if(k==-1)
		break;
	    vis[k]=true;
		for(int j=1;j<=n;j++)
		{
			if(map[k][j]!=0&&vis[j]==false&&dis[k]+map[k][j]<dis[j]) 
			{
				dis[j]=dis[k]+map[k][j];
			}
		}
	}
	

}


int main()
{
	int map1[505][505];
    int map2[505][505]; 
    cin>>n>>m;
    int u,v;
    for(int t=0;t<m;t++)
    {
    	
    	scanf("%d%d",&u,&v);
    	map1[u][v]=1;
    	map1[v][u]=1;
	}
	if(map1[1][n]==0)
	{
		Dijkstra(map1);
		
		if(dis[n]==INF)
		{
			cout<<"-1"<<endl;
		}
		else
		{
			cout<<dis[n]<<endl;
		}
	}
	else
	{
		for(int t=1;t<=n;t++)
		{
			for(int j=t+1;j<=n;j++)
			{
				if(map1[t][j]==0)
				{
					map2[t][j]=1;
					map2[j][t]=1;
				}
			}
		}
		Dijkstra(map2);
		if(dis[n]==INF)
		{
			cout<<"-1"<<endl;
		}
		else
		{
			cout<<dis[n]<<endl;
		}
		
	}
	
	
	return 0;
}