原題鏈接
思路： 連通圖中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)新聞熱點
疑難解答
