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
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=4E2+7;
7int n ,m;
8int road[N][N];
9int rail[N][N];
1int floyd()
2{
3 for ( int k = 1 ; k <= n ; k++)
4 for ( int i = 1 ; i <= n ; i++)
5 for ( int j = 1 ; j <= n ; j++)
6 if (rail[i][j]>rail[i][k]+rail[k][j]) rail[i][j] = rail[i][k] + rail[k][j];
7 if (rail[1][n]==inf) return -1;
8 else return rail[1][n];
9}
1int floyd2()
2{
3 for ( int k = 1 ; k <= n ; k++)
4 for ( int i =1 ; i <= n ; i++)
5 for ( int j = 1 ; j <= n ;j++)
6 road[i][j] = min(road[i][j],road[i][k]+road[k][j]);
7 if (road[1][n]==inf) return -1;
8 else return road[1][n];
}
1void init()
2{
3 // for ( int i = 0 ; i <= 400 ; i++)
4// for ( int j = 0 ; j <= 400 ; j ++)
5// {
6// rail[i][j] = 99999;
7// road[i][j]= 99999;
8// }
9 ms(rail,0x3f);
10 ms(road,0x3f);
11}
1int main()
2{
3 #ifndef ONLINE_JUDGE
4 freopen("code/in.txt","r",stdin);
5 #endif
1 cin>>n>>m;
2 init();
3// cout<<road[1]<<inf<<endl;
4 for ( int i = 0 ; i < m ; i++)
5 {
6 int u,v;
7 scanf("%d %d",&u,&v);
8 rail[u][v] = 1;
9 rail[v][u] = 1;
10 }
1 for ( int i = 1 ; i <= n-1 ; i++)
2 {
3 for ( int j = i+1 ; j <= n ; j++)
4 {
5 // cout<<"aaaa?"<<endl;
6 if (rail[i][j]==inf)
7 {
8 road[i][j] = 1;
9 road[j][i] = 1;
10 }
11 }
12 }
13 int ans;
14 if (rail[1][n]==1)
15 {
16 ans = floyd2();
17 cout<<ans<<endl;
18 }
19 else
20 {
1 // cout<<"aaa?"<<endl;
2 ans = floyd();
3 cout<<ans<<endl;
4 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}