51Nod 1649 齐头并进 最短路

51Nod 1649 齐头并进 最短路

分别对公路和铁路进行最短路径计算，然后判断两个路径的最大值

题目很多让你误解的地方，例如不能同时在一个站台停。

或者说每条路可以用多次

因为所有的路径都是相连的。所以在相同的步数不可能同时在一个点

题目说的汽车的路线最短情况应该是1--4 一小时到达

#include<iostream>  
#include<queue>  
#include<vector>  
#include<stack>  
#include<algorithm>
#include<cmath> 
#include<set>
#include<map>
#include<cstdio>
using namespace std;
const int INF=1<<30;
int _map[500][500]={0};
int len1[500],len2[500];
int v[500];
int n,m;
void dij1(int x){for(int i=0;i<=n;i++) v[i]=0,len1[i]=INF;len1[x]=0;queue<int> que;que.push(x);while(que.size()){int num=que.front();que.pop();if(v[num]) continue;v[num]=1;for(int i=1;i<=n;i++){if(i!=num&&_map[num][i]==1){if(len1[i]>len1[num]+1){len1[i]=len1[num]+1;que.push(i);}}}}
}
void dij2(int x){for(int i=0;i<=n;i++) v[i]=0,len2[i]=INF;len2[x]=0;queue<int> que;que.push(x);while(que.size()){int num=que.front();que.pop();if(v[num]) continue;v[num]=1;for(int i=1;i<=n;i++){if(i!=num&&_map[num][i]==0){if(len2[i]>len2[num]+1){len2[i]=len2[num]+1;que.push(i);}}}}
}
int main(){scanf("%d%d",&n,&m);for(int i=0;i<m;i++){int a,b;scanf("%d%d",&a,&b);_map[a][b]=_map[b][a]=1;}dij1(1);dij2(1);if(len1[n]==INF||len2[n]==INF){printf("-1");}else printf("%d",max(len1[n],len2[n]));return 0;}