Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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了。
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月22日 星期二 16时28分59秒
4File Name :code/cf/#333/C.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=4E2+7;
34int n ,m;
35int road[N][N];
36int rail[N][N];
37
38int floyd()
39{
40 for ( int k = 1 ; k <= n ; k++)
41 for ( int i = 1 ; i <= n ; i++)
42 for ( int j = 1 ; j <= n ; j++)
43 if (rail[i][j]>rail[i][k]+rail[k][j]) rail[i][j] = rail[i][k] + rail[k][j];
44 if (rail[1][n]==inf) return -1;
45 else return rail[1][n];
46}
47
48int floyd2()
49{
50 for ( int k = 1 ; k <= n ; k++)
51 for ( int i =1 ; i <= n ; i++)
52 for ( int j = 1 ; j <= n ;j++)
53 road[i][j] = min(road[i][j],road[i][k]+road[k][j]);
54 if (road[1][n]==inf) return -1;
55 else return road[1][n];
56
57}
58
59void init()
60{
61 // for ( int i = 0 ; i <= 400 ; i++)
62// for ( int j = 0 ; j <= 400 ; j ++)
63// {
64// rail[i][j] = 99999;
65// road[i][j]= 99999;
66// }
67 ms(rail,0x3f);
68 ms(road,0x3f);
69}
70
71int main()
72{
73 #ifndef ONLINE_JUDGE
74 freopen("code/in.txt","r",stdin);
75 #endif
76
77 cin>>n>>m;
78 init();
79// cout<<road[1]<<inf<<endl;
80 for ( int i = 0 ; i < m ; i++)
81 {
82 int u,v;
83 scanf("%d %d",&u,&v);
84 rail[u][v] = 1;
85 rail[v][u] = 1;
86 }
87
88 for ( int i = 1 ; i <= n-1 ; i++)
89 {
90 for ( int j = i+1 ; j <= n ; j++)
91 {
92 // cout<<"aaaa?"<<endl;
93 if (rail[i][j]==inf)
94 {
95 road[i][j] = 1;
96 road[j][i] = 1;
97 }
98 }
99 }
100 int ans;
101 if (rail[1][n]==1)
102 {
103 ans = floyd2();
104 cout<<ans<<endl;
105 }
106 else
107 {
108
109 // cout<<"aaa?"<<endl;
110 ans = floyd();
111 cout<<ans<<endl;
112 }
113
114
115 #ifndef ONLINE_JUDGE
116 fclose(stdin);
117 #endif
118 return 0;
119}