題目鏈接：點擊查看

題目大意：求次短路

題目分析：唉，限時訓練的時候遇到的這個題，明明之前系統學習過次短路和次小生成樹這個方面的知識的，可能是很長時間沒

用，板子都忘掉了，不過還好，在考試的時候想到了另一種方法勉強把這個題給A了，正好借助這個題來整理一下次短路的幾種

方法吧，好像是一共有三種，分別是迪杰斯特拉維護兩個數組，兩次迪杰斯特拉+枚舉邊，迪杰斯特拉+A星，不過現在我還沒接

觸過A星算法，這里就先整理前兩種方法吧（其實掌握一種就夠用了？），以后如果學會了在隨緣整理。

都是板子，也沒什么好分析的，直接掛上以后多復習多練習吧：

兩次迪杰斯特拉+枚舉：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;int n,m;struct Node {int to,w;Node(int TO,int W){to=TO;w=W;} };vector<Node>node[N];int d[N],d2[N];bool vis[N];void spfa(int x)//我比較喜歡用spfa，所以這里的用spfa代替迪杰斯特拉了，同樣是求單源最短路 {memset(d,inf,sizeof(d));memset(vis,false,sizeof(vis));vis[x]=true;d[x]=0;queue<int>q;q.push(x);while(!q.empty()){int tem=q.front();q.pop();vis[tem]=false;for(int i=0;i<node[tem].size();i++){Node temp=node[tem][i];if(d[temp.to]>d[tem]+temp.w){d[temp.to]=d[tem]+temp.w;if(!vis[temp.to]){q.push(temp.to);vis[temp.to]=true;}}}} }int main() { // freopen("input.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)node[i].clear();for(int i=1;i<=m;i++)//因為這個題是個無向圖，所以處理起來比較簡單，如果是個有向圖，需要 //開兩個數組分別儲存正向的邊和反向的邊，兩次迪杰斯特拉一次求以1為起點的正向邊和以n為起點的反向邊{int a,b,c;scanf("%d%d%d",&a,&b,&c);node[a].push_back(Node(b,c));node[b].push_back(Node(a,c));}spfa(1);for(int i=1;i<=n;i++)d2[i]=d[i];spfa(n);int ans=inf;for(int i=1;i<=n;i++)//枚舉每一條邊{for(int j=0;j<node[i].size();j++)//d2中存的是從1到各點的距離，d中存的是從n到個點的距離{int u=i;int v=node[i][j].to;int w=node[i][j].w;int temp=d2[u]+d[v]+w;if(temp>d2[n]&&temp<ans){ans=temp;}}}cout<<ans<<endl;}return 0; }

spfa維護兩個數組：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;int n,m;struct Node {int to,w;Node(int TO,int W){to=TO;w=W;} };vector<Node>node[N];int d[N],d2[N];//d維護最短路，d2維護次短路bool vis[N];void spfa(int x) {memset(d,inf,sizeof(d));memset(d2,inf,sizeof(d2));memset(vis,false,sizeof(vis));vis[x]=true;d[x]=0;queue<int>q;q.push(x);while(!q.empty()){int tem=q.front();q.pop();vis[tem]=false;for(int i=0;i<node[tem].size();i++){Node temp=node[tem][i];if(d[temp.to]>d[tem]+temp.w)//如果該邊可以更新最短路，則先將次短路更新為最短路，再更新最短路{d2[temp.to]=d[temp.to];d[temp.to]=d[tem]+temp.w;if(!vis[temp.to]){q.push(temp.to);vis[temp.to]=true;}}else if(d2[temp.to]>d[tem]+temp.w&&d[temp.to]<d[tem]+temp.w)//否則查看是否可以更新次短路{d2[temp.to]=d[tem]+temp.w;if(!vis[temp.to]){q.push(temp.to);vis[temp.to]=true;}}if(d2[temp.to]>d2[tem]+temp.w)//判斷是否可以更新次短路{d2[temp.to]=d2[tem]+temp.w;if(!vis[temp.to]){vis[temp.to]=true;q.push(temp.to);}}}} }int main() { // freopen("input.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)node[i].clear();for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);node[a].push_back(Node(b,c));node[b].push_back(Node(a,c));}spfa(1);cout<<d2[n]<<endl;}return 0; }

迪杰斯特拉維護兩個數組：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> #include<cmath> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;int n,m;struct Node {int to,w;Node(int TO,int W){to=TO;w=W;} };vector<Node>node[N];int d[N],d2[N];struct No {int d,from;No(int FROM,int D){from=FROM;d=D;}bool operator<(const No& a)const{return d>a.d;} };void Dijkstra(int x) {priority_queue<No>q;memset(d,inf,sizeof(d));memset(d2,inf,sizeof(d2));d[x]=0;q.push(No(x,0));while(!q.empty()){No tem=q.top();q.pop();int u=tem.from;if(d2[u]<tem.d)//如果取出的值比次小值還小，則肯定無法更新，從而舍棄掉 //這里算是新學到了一種全新的判斷邊界的方法，可以省去一個vis數組，就是利用優先隊列中的值與d數組中的值比較 //最短路中的模板是判斷(d[tem.from]!=tem.d)是否成立，如果不成立說明無法更新，反之可以更新 continue;for(int i=0;i<node[u].size();i++){Node temp=node[u][i];int v=temp.to;int w=temp.w;int dd=tem.d+w;if(d[v]>dd){swap(d[v],dd);q.push(No(v,d[v]));}if(d2[v]>dd&&d[v]<dd)//一定記住這里是if，不是else if，WA了不知道多少發{d2[v]=dd;q.push(No(v,d2[v]));}}} }int main() { // freopen("input.txt","r",stdin);while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++)node[i].clear();for(int i=1;i<=m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);node[a].push_back(Node(b,c));node[b].push_back(Node(a,c));}Dijkstra(1);cout<<d2[n]<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 3255 Roadblocks(次短路)的全部內容，希望文章能夠幫你解決所遇到的問題。

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