某国家有 n 个城市（编号 1∼n）和 m 条双向铁路。
每条铁路连接两个不同的城市，没有两条铁路连接同一对城市。
除了铁路以外，该国家还有公路。
对于每对不同的城市 x,y，当且仅当它们之间没有铁路时，它们之间会存在一条双向公路。
经过每条铁路或公路都需要花费 1 小时的时间。
现在有一列火车和一辆汽车同时离开城市 1，它们的目的地都是城市 n。
它们不会在途中停靠（但是可以在城市 n 停靠）。
火车只能沿铁路行驶，汽车只能沿公路行驶。
请你为它们规划行进路线，每条路线中可重复经过同一条铁路或公路，但是为了避免发生事故，火车和汽车不得同时到达同一个城市（城市 n 除外）。
请问，在这些条件的约束下，两辆车全部到达城市 n 所需的最少小时数，即求更慢到达城市 n 的那辆车所需的时间的最小值。
注意，两辆车允许但不必要同时到达城市 n。
输入格式
第一行包含整数 n 和 m。
接下来 m 行，每行包含两个整数 u,v，表示城市 u 和城市 v 之间存在一条铁路。
输出格式
一个整数，表示所需的最少小时数。
如果至少有一辆车无法到达城市 n，则输出 −1。
数据范围
前 6 个测试点满足 2≤n≤10，0≤m≤10。
所有测试点满足 2≤n≤400，0≤m≤n(n−1)/2，1≤u,v≤n。
输入样例1：
4 2
1 3
3 4
输出样例1：
2
输入样例2：
4 6
1 2
1 3
1 4
2 3
2 4
3 4
输出样例2：
-1
输入样例3：
5 5
4 2
3 5
4 5
5 1
1 2
输出样例3：
3
题解分析：直接求两种方式从1 到达 n 的最大时间就是答案
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 500;
int g[N][N],t[N][N];
int n,m;
int floyd(int a[][N])
{
for(int k=1; k<=n; ++k){
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
a[i][j] = min(a[i][j],a[i][k] + a[k][j]);
}
}
}
return a[1][n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(t,0x3f,sizeof(t));
memset(g,0x3f,sizeof(g));
for(int i=0; i<m; ++i){
int u,v;
scanf("%d%d", &u, &v);
t[u][v] = t[v][u] = 1;
}
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
if(i!=j && t[i][j]!=1)
g[i][j] = 1;
}
}
int ans = max(floyd(t),floyd(g));
if(ans == INF) ans = -1;
printf("%d\n",ans);
return 0;
}
