問題描述

蒜頭君陷入了坐標系上的一個迷陣，迷陣上有 n 個點，編號從 1 到 n。蒜頭君在編號為 1 的位置，他想到編號為 n 的位置上。蒜頭君當然想盡快到達目的地，但是他覺得最短的路徑可能有風險，所以他會選擇第二短的路徑。現(xiàn)在蒜頭君知道了 n 個點的坐標，以及哪些點之間是相連的，他想知道第二短的路徑長度是多少。
注意，每條路徑上不能重復經(jīng)過同一個點。
輸入格式
第一行輸入兩個整數(shù) n (1≤n≤200) 和 m，表示一共有 n 個點和 m 條邊。
接下來輸入 n 行，每行輸入兩個整數(shù)xi,yi(?500≤xi,yi≤500)，代表第 ii 個點的坐標。
接下來輸入 mm 行，每行輸入兩個整數(shù) pj,qj(1≤pj,qj≤n)，表示點pj和點 qj之間相連。
輸出格式
輸出一行，輸出包含一個數(shù)，表示第二短的路徑長度（小數(shù)點后面保留兩位），如果第一短路徑有多條，則答案就是第一最短路徑的長度；如果第二最短路徑不存在，則輸出 ?1。
樣例輸入
3 3
1 1
2 2
3 2
1 2
2 3
1 3
樣例輸出
2.41

思路

先求出最短路，然后在依次刪除這條最短路上的點及相連的邊，每刪一求次出此時的最短路即為次短路，取所有次短路中最小值即為此圖的次短路，提示：對最短路為起點到終點僅有一條有向邊的情況需要特殊處理

#include<bits/stdc++.h> #include<cstring> using namespace std;const int N = 205;vector<int> v_pos[N];double g[N][N];double dis[N];bool vis[N];int n, m;int pre[N]; //用一個數(shù)組記錄當前點是由哪個點更新的，例如pre[2] = 1 ,即結點2由1更新得到void Dijkstra(int u,int dele_v){memset(dis,0x7f,sizeof dis);dis[u] = 0;pre[1] = 1; //結點1由自身得到的for(int i = 0 ;i < n; ++i){double min_d = dis[0];int min_v = -1;for(int j = 1; j <= n; ++j){if(j != dele_v && !vis[j] && dis[j] < min_d){min_d = dis[j];min_v = j;}}if(min_v == -1){ //說明單源最短路已經(jīng)找齊return;}vis[min_v] = true; //標記for(int k = 1; k <= n; ++k){ //遍歷和j相鄰的點if(k != dele_v && min_v != k && !vis[k] && dis[k] > min_d + g[min_v][k]){dis[k] = min_d + g[min_v][k];pre[k] = min_v;}}} }int main(){memset(g,0x7f,sizeof g);cin >> n >> m;int i = 1;int t = n;while(t--){int x,y;cin >> x >> y;v_pos[i].push_back(x);v_pos[i].push_back(y);++i;}while(m--){int u,v;cin >> u >> v;double len = sqrt((v_pos[u][0]-v_pos[v][0])*(v_pos[u][0]-v_pos[v][0])+(v_pos[u][1]-v_pos[v][1])*(v_pos[u][1]-v_pos[v][1]));g[u][v] = g[v][u] = len;}Dijkstra(1,0);double ans = g[0][0];if(pre[n] == 1){ //如果剛好從1到n最短路前一個結點就是1，即最短路就是1和n的邊權，需要特殊處理g[1][n] = g[n][1] = g[0][0]; //刪除從1到n的無向邊memset(vis,0,sizeof vis); //注意！！！！ 每用一次Dijkstra，就得重置一次visDijkstra(1,0);ans = min(ans,dis[n]);}else{ //否則，依次刪去最短路除頭尾結點的各個結點，再進行Dijkstra算法，找出刪去結點的最短路的最小值，即次短路for(int p = pre[n]; p != 1; p = pre[p]){memset(vis,0,sizeof vis); //注意！！！！ 每用一次Dijkstra，就得重置一次visDijkstra(1,p); //對最短路上有其他點的情況，只需依次刪除點即可ans = min(dis[n], ans);}}printf("%.2f\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的迷阵突围——Dijkstra求次短路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。