齐头并进

齐头并进

在一个叫奥斯汀的城市，有n个小镇（从1到n编号），这些小镇通过m条双向火车铁轨相连。当然某些小镇之间也有公路相连。为了保证每两个小镇之间的人可以方便的相互访问，市长就在那些没有铁轨直接相连的小镇之间建造了公路。在两个直接通过公路或者铁路相连的小镇之间移动，要花费一个小时的时间。

现在有一辆火车和一辆汽车同时从小镇1出发。他们都要前往小镇n，但是他们中途不能同时停在同一个小镇（但是可以同时停在小镇n）。火车只能走铁路，汽车只能走公路。

现在请来为火车和汽车分别设计一条线路；所有的公路或者铁路可以被多次使用。使得火车和汽车尽可能快的到达小镇n。即要求他们中最后到达小镇n的时间要最短。输出这个最短时间。(最后火车和汽车可以同时到达小镇n，也可以先后到达。)

样例解释：

在样例中，火车可以按照 1⟶3⟶4 行驶，汽车 1⟶2⟶4 按照行驶，经过2小时后他们同时到过小镇4。

输入
单组测试数据。
第一行有两个整数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

题意：从1出发到n，任意两点之间肯定有路，不是铁路就是公路，在两个直接通过公路或者铁路相连的小镇之间移动，要花费一个小时的时间。两点之间现在有一辆火车和一辆汽车同时从1出发去n，两辆车不能同时停留在同一点，两辆车都走最短路，求两辆车晚到的那辆的最短时间。
思路：这个题乍一看上去听麻烦，仔细一想其实并不难，任意两点之间都有路，不是铁路就是公路，也就是说火车和汽车肯定有一个用一小时就能到达，所以肯定不存在同时停在同一点的情况，所以找出那条不能直接到达n点的路求最小短路就行，数据量也不大，佛洛依德就能行。
代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int a[1001][1001];
int INF=0x3f3f3f;
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==j)a[i][j]=0;elsea[i][j]=INF;}for(int i=0;i<m;i++){int x,y;cin>>x>>y;a[x][y]=1;a[y][x]=1;}if(a[1][n]==1){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][j]=a[i][j]==1?INF:1;}}}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i!=j)a[i][j]=min(a[i][j],a[i][k]+a[k][j]);}if(a[1][n]!=INF)cout<<a[1][n]<<endl;elsecout<<-1<<endl;
}

理解题目后并不难，但是这个题错了好多遍，有两个地方出错了，一个是佛洛依德的K循环写到最下面去了，当时真是没过脑子，还有就是双目运算符写错了，之前没大用过，网上的题解都是Dijkstra，但我感觉我的代码没毛病，可是就过不了，测试数据还不好想，本来想省点事来这却花了一个下午来查错。。。。。