題目描述

每天早晨，FJ從家中穿過農場走到牛棚。農場由 N 塊農田組成，農田通過 M 條雙向道路連接，每條路有一定長度。FJ 的房子在 1 號田，牛棚在 N 號田。沒有兩塊田被多條道路連接，以適當的路徑順序總是能在農場任意一對田間行走。當FZ從一塊田走到另一塊時，總是以總路長最短的道路順序來走。

FJ 的牛呢，總是不安好心，決定干擾他每天早晨的計劃。它們在 M 條路的某一條上安放一疊稻草堆，使這條路的長度加倍。牛希望選擇一條路干擾使得FJ 從家到牛棚的路長增加最多。它們請你設計并告訴它們最大增量是多少。

輸入輸出格式

輸入格式：

?

第 1 行：兩個整數 N, M。

第 2 到 M+1 行：第 i+1 行包含三個整數 A_i, B_i, L_i，A_i 和 B_i 表示道路 i 連接的田的編號，L_i 表示路長。

?

輸出格式：

?

第 1 行：一個整數，表示通過使某條路加倍而得到的最大增量。

?

輸入輸出樣例

輸入樣例#1：
5 7 2 1 5 1 3 1 3 2 8 3 5 7 3 4 3 2 4 7 4 5 2 輸出樣例#1：
2

說明

【樣例說明】

若使 3 和 4 之間的道路長加倍，最短路將由 1-3-4-5 變為 1-3-5。

【數據規模和約定】

對于 30%的數據，N <= 70，M <= 1,500。

對于 100%的數據，1 <= N <= 100，1 <= M <= 5,000，1 <= L_i <= 1,000,000。

?

題目大意：求將1--n上最短路的某條邊的邊權*2后新的最短路與原最短路長度差最大是多少

題解：暴力枚舉最短路的每一條邊*2再跑最短路取max

代碼：

?

#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std;queue<int>q; int n,m,sumedge,cnt,cur,ans; int head[110],pre[110],cut[1100],bege[1100],dis[110],inq[110];struct Edge{int x,y,z,nxt;Edge(int x=0,int y=0,int z=0,int nxt=0):x(x),y(y),z(z),nxt(nxt){} }edge[5002*2];void add(int x,int y,int z){edge[++sumedge]=Edge(x,y,z,head[x]);head[x]=sumedge; }int spfa(){memset(dis,127/3,sizeof(dis));memset(inq,0,sizeof(inq));while(!q.empty())q.pop();q.push(1);dis[1]=0;inq[1]=1;while(!q.empty()){int now=q.front();q.pop();inq[now]=0;for(int i=head[now];i;i=edge[i].nxt){int v=edge[i].y;if(dis[v]>dis[now]+edge[i].z){dis[v]=dis[now]+edge[i].z;pre[v]=now;bege[v]=i;if(!inq[v]){inq[v]=1;q.push(v);}}}}return dis[n]; }int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}cur=spfa(); // cout<<dis[3]<<" "<<dis[4]<<endl;for(int i=n;i;i=pre[i])cut[++cnt]=bege[i];for(int i=1;i<=cnt;i++){int k=cut[i];// cout<<k<<endl;if(k&1){edge[k].z*=2;edge[k+1].z*=2;}else {edge[k].z*=2;edge[k-1].z*=2;}ans=max(ans,spfa());if(k&1){edge[k].z/=2;edge[k+1].z/=2;}else{edge[k].z/=2;edge[k-1].z/=2;}} // cout<<ans<<" "<<cur<<endl;cout<<ans-cur<<endl;return 0; }

?

轉載于:https://www.cnblogs.com/zzyh/p/7601923.html

總結

以上是生活随笔為你收集整理的P2176 [USACO14FEB]路障Roadblock的全部內容，希望文章能夠幫你解決所遇到的問題。

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