題目大意：在一個圖上有許多個農場，有個人從1農場出發，到他的朋友n農場去，他不想走一條最短路徑，這次他想換條路走，要你幫他找一條次短路徑，次短路的定義是，比最短路徑長度短（可能有多條），但是不會比其他的路徑長度長。而且告訴你數據中一定存在至少一條次短路。

解題思路：大致的分析下，如果我們用常規思想做這題：
刪除某一條邊求最短路徑，找出的最短路徑比最短路徑短，但是比其他路徑長就是的了
這樣做的時間復雜度是，spfa的時間復雜度大約是O(KE),E為邊的總數=200000
然后枚舉邊O(E),那么總的時間復雜度為O(KE^2),大約是K*400億。這樣明顯會超時。

最短路明顯不會是次短路,因為題目說了次短一定是存在的，那么他們不可能重合，這樣次短路肯定是最短路中某一條邊不走，而走了其他邊再回到最短路上，而且不可能繞兩個地方，只可能繞一個地方，因為明顯繞兩個地方比繞一個地方的路徑長，明顯不是次短路了
所以我們枚舉每條邊<s,t>
有dis[s]---源點到s的最短距離
有rdis[t]----t到匯點的最短距離，這樣就需要從t到s求一次最短路得到了
len<s,t>表示<s,t>這條邊的長度
然后我們枚舉每一條邊有：tmp=d[s]+dr[t]+len<s,t>
找出其中比最短路小但是比其他路長的一個值就是次短路徑了

#include <iostream> #include <cstdio> #include <cstring> #include <queue> #define MAX 1e9 #define MAXE 200100 using namespace std; struct edge {int v,w,n; }e[MAXE]; int n,m; int head[10000],num,dis[10000],in[10000],rdis[10000]; void add(int a,int b,int c)//這個數據結構感覺好難懂 {e[num].v=b;e[num].w=c;e[num].n=head[a];head[a]=num;num++; } void SPFA(int k,int d[]) {for(int i=1;i<=n;i++)d[i]=MAX;d[k]=0;memset(in,0,sizeof in);queue <int> q;q.push(k);in[k]=1;while(!q.empty()){int t;t=q.front();q.pop();in[t]=0;for(int i=head[t];i!=-1;i=e[i].n)//{int v=e[i].v;int w=e[i].w;if(d[v]>d[t]+w){d[v]=d[t]+w;if(in[v]==0){in[v]=1;q.push(v);}}}} } int main() {while(scanf("%d%d",&n,&m)!=EOF){memset(head,-1,sizeof head);num=0;for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);add(a,b,c);add(b,a,c);}SPFA(1,dis);SPFA(n,rdis);int ans=MAX;for(int i=1;i<=n;i++)for(int j=head[i];j!=-1;j=e[j].n){int v=e[j].v;int w=e[j].w;int temp=dis[i]+rdis[v]+w;if(temp>dis[n]&&ans>temp)ans=temp;}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的poj 3255 Roadblocks （SPFA）的全部內容，希望文章能夠幫你解決所遇到的問題。

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