桐人的約會

題目大意：

刪掉一條邊，讓一個圖中的最短路最長

原題：

題目描述

這是一個風和日麗的日子，桐人和詩乃在約會。他們所在的城市共有N個街區(qū)，和M條道路，每條道路連接兩個不同的街區(qū)，并且通過一條道路需要花費一些時間。他們現(xiàn)在處于N號街區(qū)，正在享受幸福時光的桐人完全忘記了他的手機被亞絲娜安裝了監(jiān)控裝置的事情，此時亞絲娜已經(jīng)得知了桐人的位置以及他正在和一個妹子約會的事實，十分憤怒，于是從她所在的1號街區(qū)火速趕往N號街區(qū)。現(xiàn)在這個城市中有一條道路正在維修，不能通行，不過不論是哪條道路處于維修中，均存在一條路徑可以從1號街區(qū)前往N號街區(qū)，而且亞絲娜一定會選取最短路前往N號街區(qū)。現(xiàn)在你很好奇，桐人的美好時光最多還能持續(xù)多久，即亞絲娜最多要花費多長的時間才能到達N號街區(qū)。

輸入

第1行：兩個正整數(shù)N，M，N表示街區(qū)個數(shù)，M表示道路數(shù)。
第2到M+1行 每行三個整數(shù) u,v,w 表示存在一條連接u和v的道路，通過這條道路花費的時間為w
數(shù)據(jù)保證沒有重邊和自環(huán)

輸出

一個整數(shù)，表示最多花費的時間。

輸入樣例

5 7 1 2 8 1 4 10 2 3 9 2 4 10 2 5 1 3 4 7 3 5 10

輸出樣例

27

說明

【數(shù)據(jù)規(guī)模】

30% N<=5, M<=10
60% N<=1000,M<=10000,w=1
100% N<=1000, M<=N*(N-1)/2,1<=w<=1000

解題思路：

先找到最短路，然后將最短路中的每一段路依次刪掉，每刪掉一次跑一遍SPFA

代碼：

#include<queue> #include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m,w,h,x,y,c,ans,p[1005],b[1005],la[1005],las[1005],head[1005]; struct rec {int l,to,next,pd; }a[2000005]; void SPFA(int now) {a[now].pd=1;//去掉memset(b,127/3,sizeof(b));queue<int>d;//SPFAd.push(1);p[1]=1;b[1]=0;while(!d.empty()){h=d.front();d.pop();for (int i=head[h];i;i=a[i].next)if (b[h]+a[i].l<b[a[i].to]&&(!a[i].pd)){b[a[i].to]=b[h]+a[i].l;if (!p[a[i].to]){p[a[i].to]=1;d.push(a[i].to);}}p[h]=0;}a[now].pd=0;//返回ans=max(ans,b[n]);//取最大值 } void spfa()//SPFA {memset(b,127/3,sizeof(b));queue<int>d;d.push(1);p[1]=1;b[1]=0;while(!d.empty()){h=d.front();d.pop();for (int i=head[h];i;i=a[i].next)if (b[h]+a[i].l<b[a[i].to]){b[a[i].to]=b[h]+a[i].l;las[a[i].to]=h;//前綴la[a[i].to]=i;//相連接的線if (!p[a[i].to]){p[a[i].to]=1;d.push(a[i].to);}}p[h]=0;}for (int i=n;i>1;i=las[i])SPFA(la[i]);//刪掉這條線路再跑最短路 } int main() {scanf("%d %d",&n,&m);for (int i=1;i<=m;++i){scanf("%d %d %d",&x,&y,&c);a[++w].to=y;//存儲a[w].l=c;a[w].next=head[x];head[x]=w;a[++w].to=x;a[w].l=c;a[w].next=head[y];head[y]=w;}spfa();//最短路printf("%d",ans); }

總結(jié)

以上是生活随笔為你收集整理的【SPFA】桐人的约会的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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