本文主要是介绍1649 齐头并进 (水)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
收藏 
关注 在一个叫奥斯汀的城市，有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。
Input示例
4 2 1 3 3 4
Output示例
2
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f using namespace std;
const int maxn = 440;int n,m;
int map[maxn][maxn],dis[maxn],vis[maxn];
int map1[maxn][maxn],dis1[maxn],vis1[maxn];
void dijkstra(int st){memset(vis,0,sizeof(vis));for(int i = 1;i<=n;i++){dis[i] = map[st][i];}vis[st] = 1;dis[st] = 0;int pos = st;for(int i = 1;i<=n-1;i++){for(int j = 1;j<=n;j++){if(!vis[j] && dis[j]>dis[pos] + map[pos][j]){dis[j]=dis[pos] + map[pos][j];}}int v,minn = INF;for(int j = 1;j<=n;j++){if(!vis[j] && minn>dis[j]){v = j;minn = dis[j];}}vis[v] = 1;pos = v;}
}
void dijkstra1(int st){memset(vis1,0,sizeof(vis1));for(int i = 1;i<=n;i++){dis1[i] = map1[st][i];}vis1[st] = 1;dis1[st] = 0;int pos = st;for(int i = 1;i<=n-1;i++){for(int j = 1;j<=n;j++){if(!vis1[j] && dis1[j]>dis1[pos] + map1[pos][j]){dis1[j]=dis1[pos] + map1[pos][j];}}int v,minn = INF;for(int j = 1;j<=n;j++){if(!vis1[j] && minn>dis1[j]){v = j;minn = dis1[j];}}vis1[v] = 1;pos = v;}
}
int main()
{memset(map,INF,sizeof(map));memset(map1,INF,sizeof(map1));scanf("%d %d",&n,&m);int a,b;for(int i = 0;i<m;i++){scanf("%d %d",&a,&b);map[a][b] = map[b][a] = 1;}if(m == 0){printf("-1\n");return 0;}else if(m==n*(n-1)/2){printf("-1\n");return 0;}for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){if(map[i][j] == INF){map1[i][j] = map1[j][i] = 1;}}}dijkstra(1);dijkstra1(1);if(dis1[n] == INF || dis[n] == INF) printf("-1\n");else printf("%d\n",max(dis[n],dis1[n]));return 0;
}
/***test1
input
5 5
4 2
3 5
4 5
5 1
1 2
output
3
-------------
test2
input
20 0
output
-1
----------------
test3
input
3 1
1 2
output
-1
****************/
这篇关于1649 齐头并进 (水)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
