本文主要是介绍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;}
这篇关于51Nod 1649 齐头并进 最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
