https://www.luogu.org/problem/show?pid=2176
题目描述
每天早晨，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 #include <cstring> 2 #include <cstdio> 3 #include <queue> 4 5 #define max(a,b) (a>b?a:b) 6 inline void read(int &x) 7 { 8 x=0; register char ch=getchar(); 9 for(;ch>'9'||ch<'0';) ch=getchar(); 10 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; 11 } 12 const int M(5005); 13 const int N(110); 14 int n,m,head[N],sumedge=1; 15 struct Edge { 16 int v,next,w; 17 Edge(int v=0,int next=0,int w=0):v(v),next(next),w(w){} 18 }edge[M<<1]; 19 inline void ins(int u,int v,int w) 20 { 21 edge[++sumedge]=Edge(v,head[u],w); head[u]=sumedge; 22 edge[++sumedge]=Edge(u,head[v],w); head[v]=sumedge; 23 } 24 25 bool inq[N]; 26 std::queue<int>que; 27 int dis[N],mindis,ansdis,pre[N],zz[N]; 28 inline int SPFA(int s) 29 { 30 for(int i=1; i<=n; ++i) 31 dis[i]=0x3f3f3f3f,inq[i]=0; 32 for(; !que.empty(); ) que.pop(); 33 que.push(s); dis[s]=0; 34 for(int u,v; !que.empty(); ) 35 { 36 u=que.front(); que.pop(); inq[u]=0; 37 for(int i=head[u]; i; i=edge[i].next) 38 { 39 v=edge[i].v; 40 if(dis[v]>dis[u]+edge[i].w) 41 { 42 zz[v]=u; dis[v]=dis[u]+edge[i].w; 43 if(!inq[v]) inq[v]=1,que.push(v); 44 } 45 } 46 } 47 return dis[n]; 48 } 49 50 int Presist() 51 { 52 read(n),read(m); 53 for(int u,v,w,i=1; i<=m; ++i) 54 read(u),read(v),read(w),ins(u,v,w); 55 mindis=SPFA(1);memcpy(&pre,&zz,sizeof(zz)); 56 for(int v,u=1; u<=n; ++u) 57 for(int i=head[u]; i; i=edge[i].next) 58 { 59 v=edge[i].v; 60 if(pre[v]==u||pre[u]==v) 61 { 62 edge[i].w<<=1; 63 edge[i^1].w<<=1; 64 ansdis=max(ansdis,SPFA(1)-mindis); 65 edge[i].w>>=1; 66 edge[i^1].w>>=1; 67 } 68 } 69 printf("%d ",ansdis); 70 return 0; 71 } 72 73 int Aptal=Presist(); 74 int main(int argc,char*argv[]){;}