codeforces #333 div 2 C. The Two Routes

http://codeforces.com/problemset/problem/602/C 题意：给出n个城镇，m条双向铁路，对于任意不同的x,y，如果x,y之间没有铁路，那么一定有双向公路。train只能走铁路，bus只能走公路。现在一辆火车和一辆bus同时从1出发，要到达n，处于安全考虑，bus和火车不能同时处在除了n以外的点。bus和train不要求同时到达。任意一段道路的时间花费都是1小时。问最少需要多久使得bus和train都到达n。如果存在某个不能到达，那么输出-1. 思路：n才400.一开始打算先按照rail和road建两个图。这两个图互为补。然后在floyd的时候加以判断。但是马上就发现。。不能同时到达同伙一个点这个条件其实不会影响。。因为按照题意，一定存在一条1到n的路，不是公路就是铁路。那么就让有路的花费1的代价到n，然后剩下的求一个一到n的最短路即可。由于n才400.。最短路怎么搞都行。。我偷懒就用floyd了。

/* ***********************************************
Author :111qqz
Created Time :2015年12月22日 星期二 16时28分59秒
File Name :code/cf/#333/C.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=4E2+7;
int n ,m;
int road[N][N];
int rail[N][N];

int floyd()
{
    for ( int k = 1 ; k <= n ; k++)
	for ( int i = 1 ; i <= n ; i++)
	    for ( int j = 1 ; j <= n ; j++)
		if (rail[i][j]>rail[i][k]+rail[k][j]) rail[i][j] = rail[i][k] + rail[k][j];
    if (rail[1][n]==inf) return -1;
	else return rail[1][n];
}

int floyd2()
{
    for ( int k = 1 ; k <= n ; k++)
	for ( int i =1 ;  i <= n ; i++)
	    for ( int j = 1 ; j <= n ;j++)
		road[i][j] = min(road[i][j],road[i][k]+road[k][j]);
    if (road[1][n]==inf) return -1;
	else return road[1][n];

}

void init()
{
  //  for ( int i = 0 ; i <= 400 ; i++)
//	for ( int j = 0 ; j <= 400 ; j ++)
//	{
//	    rail[i][j] = 99999;
//	    road[i][j]=  99999;
//	}
    ms(rail,0x3f);
    ms(road,0x3f);
}

int main()
{
	#ifndef  ONLINE_JUDGE 
	freopen("code/in.txt","r",stdin);
  #endif

	cin>>n>>m;
	init();
//	cout<<road[1]<<inf<<endl;
	for ( int i = 0 ; i < m ; i++)
	{
	    int u,v;
	    scanf("%d %d",&u,&v);
	    rail[u][v] = 1;
	    rail[v][u] = 1;
	}
	
	for ( int i = 1 ; i <= n-1 ; i++)
	{
	    for ( int j = i+1 ; j <= n ; j++)
	    {
	//	cout<<"aaaa?"<<endl;
		if (rail[i][j]==inf)
		{
		    road[i][j] = 1;
		    road[j][i] = 1;
		}
	    }
	}
	int ans;
	if (rail[1][n]==1)
	{
	    ans = floyd2();
	    cout<<ans<<endl;
	}
	else
	{
	    
	 //   cout<<"aaa?"<<endl;
	    ans = floyd();
	    cout<<ans<<endl;
	}


  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}