51Nod-1649 齐头并进

1649 齐头并进 

题目来源：  CodeForces

基准时间限制：1 秒 空间限制：131072 KB 分值: 10  难度：2级算法题

 收藏

 关注

单组测试数据。
第一行有两个整数n 和 m (2≤n≤400, 0≤m≤n*(n-1)/2) ，表示小镇的数目和铁轨的数目。
接下来m行，每行有两个整数u 和 v，表示u和v之间有一条铁路。(1≤u,v≤n, u≠v)。
输入中保证两个小镇之间最多有一条铁路直接相连。

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

4 2
1 3
3 4

2

System Message  (题目提供者)

我的思路是将图的邻接矩阵设为布尔型（待会就知道为什么了），然后输入火车线路，此时进行第一次求最短路径，结果保存在ans1里，然后将整个矩阵取非（题意两个城市之间必有铁路或公路，此时就变成了公路的邻接矩阵了），然后再对汽车求一次最短路径，结果保存在ans2里，但是，题目要求火车和汽车必须都到达n才能输出较长的到达时间，所以有三种情况：

1.火车或汽车不能到达，此时输出-1

2.火车比汽车先到达，输出汽车到达所需的时间

3.汽车比火车先到达，输出火车到达所需的时间

下面是代码↓↓↓

#include <stdio.h>
#include <string.h>
#define MAXN 410
#define INF 0x3f3f3f3fbool vis[MAXN];
bool map[MAXN][MAXN];
int path[MAXN];int Dij( int n) {//将最短路径设置为无穷大 memset( path,INF,sizeof(path) );//出发点 vis[1] = true;//更新出发点能直接到达的地方，同时其余地方设置为未到达过 for( int i=2 ; i<=n ; i++ ) {vis[i] = false;if( map[1][i] )path[i] = 1;}for( int i=1 ; i<n ; i++ ) {//记录最小值 int min = INF;//记录最小值的位置 int pos;for( int j=1 ; j<=n ; j++ ) {if( !vis[j] && min>path[j] ) {min = path[ pos=j ];}}//去往最小值 vis[pos] = true;//更新最短路径 for( int j=1 ; j<=n ; j++ ) {if( !vis[j] && map[pos][j] && path[j]>path[pos]+1 )path[j] = path[pos]+1;}}return path[n];
}//邻接矩阵取反 
void Not( int n ) {for( int i=1 ; i<=n ; i++ ) {for( int j=1 ; j<=n ; j++ ) {if( map[i][j] )map[i][j] = false;elsemap[i][j] = true;}}
}//验证矩阵取反正确性 
//void out( int n ) {
//	for( int i=1 ; i<=n ; i++ ) {
//		for( int j=1 ; j<=n ; j++ ) {
//			printf( "%d ",map[i][j] );
//		}
//		printf( "\n" );
//	}
//	printf( "\n");
//}int main() {freopen( "input.txt","r",stdin );int n,m;memset( map,false,sizeof(map) );scanf( "%d%d",&n,&m );int s,e;for( int i=0 ; i<m ; i++ ) {scanf( "%d%d",&s,&e );map[s][e] = map[e][s] = 1;}//保存火车到达时间 int ans1 = Dij(n);
//	out(n);//取反Not(n);
//	out(n);//保存汽车到达时间 int ans2 = Dij(n);//一方不能到达输出-1 if( ans1==INF || ans2==INF )printf( "-1\n" );else {//输出后到达n的最短时间 if( ans1<ans2 )printf( "%d\n",ans2 );elseprintf( "%d\n",ans1 );}
}