齐头并进 51Nod

齐头并进 51Nod

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

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

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

样例解释：

在样例中，火车可以按照 1⟶3⟶4

行驶，汽车 1⟶2⟶4

 按照行驶，经过2小时后他们同时到过小镇4。

Input 单组测试数据。
第一行有两个整数n 和 m (2≤n≤400, 0≤m≤n*(n-1)/2) ，表示小镇的数目和铁轨的数目。
接下来m行，每行有两个整数u 和 v，表示u和v之间有一条铁路。(1≤u,v≤n, u≠v)。
输入中保证两个小镇之间最多有一条铁路直接相连。 Output 输出一个整数，表示答案，如果没有合法的路线规划，输出-1。 Sample Input

4 2
1 3
3 4

Sample Output

2

思路：比赛时写的这题当时考虑了一下要不要判断这句话“他们中途不能同时停在同一个小镇”，然后画了几个图，觉得不用考虑这句话，因为两点之间肯定会有一条路，要么公路要么铁路，然后当时的想法是，建两个邻接表，跑两遍spfa，找到最大值即可，这样可以过：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<math.h>
using namespace std;
#define inf 0x3f3f3f3f
const int N=404;
int m,n,a[N],b[N],dis[N],tot,cnt,head[N],heada[N],mapp[N][N],ans1,ans2;
bool vis[N];
struct node
{int v,dis,net;
}e[N*N],ee[N*N];
void add(int a,int b,int c)//铁路邻接表
{e[tot].v=b;e[tot].dis=c;e[tot]=head[a];head[a]=tot++;
}
void adda(int a,int b,int c)//公路邻接表
{ee[cnt].v=b;ee[cnt].dis=c;ee[cnt]=heada[a];heada[a]=cnt++;
}
void spfa()
{memset(dis,0x3f,sizeof(dis));memset(vis,false,sizeof(vis));queue<int>q;q.push(1);dis[1]=0;vis[1]=true;while(!q.empty()){int u=q.front();q.pop();vis[u]=false;for(int j=head[u];j!=-1;j=e[j]){int v=e[j].v,dist=e[j].dis;if(dis[v]>dis[u]+dist){dis[v]=dis[u]+dist;if(!vis[v]){vis[v]=true;q.push(v);}}}}ans1=dis[n];memset(vis,false,sizeof(vis));memset(dis,0x3f,sizeof(dis));while(!q.empty()) q.pop();q.push(1);vis[1]=true;dis[1]=0;while(!q.empty()){int u=q.front();q.pop();vis[u]=false;for(int j=heada[u];j!=-1;j=ee[j]){int v=ee[j].v,dist=ee[j].dis;if(dis[v]>dis[u]+dist){dis[v]=dis[u]+dist;if(!vis[v]){vis[v]=true;q.push(v);}}}}if(ans1==inf||dis[n]==inf) printf("-1n");else printf("%dn",max(ans1,dis[n]));
}
int main()
{int u,v;cnt=tot=0;memset(head,-1,sizeof(head));memset(heada,-1,sizeof(heada));scanf("%d%d",&n,&m);while(m--){scanf("%d%d",&u,&v);add(u,v,1);add(v,u,1);mapp[u][v]=mapp[v][u]=1;}for(int i=1;i<=n;i++){for(int j=1;j<i;j++)if(mapp[i][j]==0){adda(i,j,1);adda(j,i,1);}}spfa();
}

不过我们再想一想，既然上面我说了，两个地点之间一定会有一路，要么公路，要么铁路，那1到n是不是也是一个道理呢，1到n要么有一条公路，要么有一条铁路，所以我们只要用那条不能直接到路来跑spfa，然后判断它是否能从1到n点。下面是室友写的代码：

#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<string.h>
#include<map>
#include<cstdio>
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int ma[500][500];
int dis[500];
int vis[500];
int n,m,a,b;
void spfa(int x)
{mem(dis,inf);mem(vis,0);dis[1]=0;queue<int>q;q.push(1);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int v=1; v<=n; v++)if(v!=u&&ma[u][v]==x)if(dis[v]>dis[u]+1){dis[v]=dis[u]+1;if(vis[v]) continue;vis[v]=1;q.push(v);}}
}
int main()
{scanf("%d%d",&n,&m);for(int i=0; i<m; i++){scanf("%d%d",&a,&b);ma[a][b]=ma[b][a]=1;}spfa(!ma[1][n]);printf("%dn",dis[n]==inf? -1:dis[n]);return 0;
}