求圖中的次短路徑

輸入格式

第一行輸入兩個整數(shù)?$n$?($1\le n\le 200$) 和?$m$，表示一共有?$n$?個點和?$m$?條邊。

接下來輸入$n$?行，每行輸入兩個整數(shù)xi?,yi??(?500≤xi?,yi?≤500)，代表第$i$?個點的坐標。

接下來輸入?$m$?行，每行輸入兩個整數(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

解題說明：不允許重復節(jié)點的次短路徑，先dijksta算法算出最短路徑，并記錄1—>n最短路的路徑。

問題的關鍵是怎么記錄1—>n節(jié)點最短路徑？我們用一個fa[maxn]數(shù)組，不斷保存某一節(jié)點被何now節(jié)點更新。比如最短路徑是1->2->3->4，那我們dijkstra算法是，每次更新，就會保存1節(jié)點到當前搜索節(jié)點的最短路徑，那1到該節(jié)點怎么來的，是直接1來，還是經過其他點更新來的，發(fā)fa[]就是記錄這個點上一步是誰更新來的。這里發(fā)fa[3]=2,fa[2]=1;fa[4]=3;

我們枚舉剔除最短路勁上的邊，就可以從邊（fa[n]——n）開始了。

最后memset賦值double（較大值如0x3f3f3f3f）是不行的.

ac代碼：

#include<iostream> #include<cstdio> #include<vector> #include<cmath> #include<string.h> #include<map> using namespace std; const int MAXN=205; double inf=99999999; struct po{int x, y; }p[MAXN]; int fa[MAXN]; struct node{int no;double cow;node(int noo,double coww){no=noo;cow=coww;} }; double dis[MAXN]; int n; bool mark[MAXN]; vector<node>ve[MAXN]; void dij(int left,int right){int now=1;dis[1]=0;memset(mark,false,sizeof(mark));mark[1]=true;for(int i=2;i<=n;i++) dis[i]=inf; for(int i=1;i<n;i++){for(int j=0;j<ve[now].size();++j){if(mark[ve[now][j].no]||(now==left&&ve[now][j].no==right)||(now==right&&ve[now][j].no==left))continue;if(dis[ve[now][j].no]>dis[now]+ve[now][j].cow){if(!right&&!left)fa[ve[now][j].no]=now;dis[ve[now][j].no]=dis[now]+ve[now][j].cow;} }int mn=inf;for(int i=1;i<=n;i++){if(mark[i])continue;if(dis[i]<mn){mn=dis[i];now=i;}}mark[now]=true;} } int main(){int m;cin>>n>>m;memset(mark,false,sizeof(mark));for(int i=1;i<=n;i++){int ip1,ip2;cin>>ip1>>ip2;p[i].x=ip1;p[i].y=ip2;}for(int i=1;i<=m;i++){int ip1,ip2;cin>>ip1>>ip2;double lo=sqrt((p[ip1].x-p[ip2].x)*(p[ip1].x-p[ip2].x)+(p[ip1].y-p[ip2].y)*(p[ip1].y-p[ip2].y));ve[ip1].push_back(node(ip2,lo));ve[ip2].push_back(node(ip1,lo));}dij(0,0);if(dis[n]==inf){cout<<"-1"<<endl;return 0;}double mn=inf;int now=n;fa[1]=0;while(fa[now]){ dij(fa[now],now); mn=min(dis[n],mn); now=fa[now]; } if(mn==inf)cout<<"-1"<<endl;else printf("%.2lf",mn);return 0; }

總結

以上是生活随笔為你收集整理的迷阵突围（dijkstra求次短路径）的全部內容，希望文章能夠幫你解決所遇到的問題。

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