原题链接
思路： 连通图中1和n之间是直接连接的，该路是某种交通工具的最短路径（为1），只需用dijkstra求出另一种交通工具的最短路径就能得到答案。 PS：由于路径较短的是1到n直达，不经过其间任意一点，所以题目中要求的两种交通工具不能到达同一点（除1和n）的条件其实不用考虑。
AC代码：
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>#include <queue>#include <vector> #define INF 100000000using namespace std;int n,m;int rail[405][405],road[405][405];int d[405];bool use[405];int sum,min1,min2;void Dijkstra(int dis[405][405]){ int i; fill(d + 1, d + 1 + n, INF); use[1] = use[n] = false; d[1] = 0; while(true){ int v = -1; for(i = 1; i <= n; i++){ if(!use[i] && (v == -1 || d[i] < d[v])) v = i; } if(v == -1) break; use[v] = true; for(i = 1; i <= n; i++){ if(!use[i]) d[i] = min(d[i], d[v] + dis[v][i]); //cout<<i<<' '<<d[i]<<endl; } } if(d[n] == INF) PRintf("-1/n"); else printf("%d/n",d[n]);}int main(){ int i; bool flag = false; //判断地铁能否直达 scanf("%d %d", &n, &m); for(i = 1; i <= n; i++){ fill(rail[i] + 1, rail[i] + 1 + n, INF); fill(road[i] + 1, road[i] + 1 + n, 1); rail[i][i] = road[i][i] = 0; } for(i = 0; i < m; i++){ int u,v; scanf("%d %d",&u,&v); if((u == 1 && v == n) || (u == n && v == 1)) flag = true; rail[u][v] = rail[v][u] = 1; road[u][v] = road[v][u] = INF; } if (m == n*(n-1)/2) { //地铁把所有路都占了 printf("-1/n"); } else if (flag == 1){ //地铁能直达 Dijkstra(road); } else{ //地铁不能直达 Dijkstra(rail); } return 0;}新闻热点
疑难解答
