3.道路阻塞（rblock）

题目描述

每天早上，约翰都要从他的家里步行去农场，他途中可能要经过其他的一些地方。我们把这些地方和路抽象成一张图，这张图里有N个点，共有M条边（每条边都是双向边），每条边都有一个长度，约翰的家在第1个点，农场在第N个点，两个点之间没有重复的边，并且这个图是一个连通图，每次约翰从家里到农场总会选一条最短的路径走。
但是约翰的奶牛们老是给约翰捣乱，奶牛们计划在其中某条路上放一些干草堆来阻碍约翰的行走，干草堆放在哪条路上，那条边的长度就相当于增加了一倍。现在，奶牛们想要知道如何选择一条边放干草堆，才能使约翰从家里到农场花费的路程增加最多。

输入

第一行是两个正整数N和M。
接下来M行，每行三个整数a，b，c表示点a到点b的距离是c。

输出

输出从家里到农场的最短路径最多会增加的距离。

样例输入

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

样例输出

2

数据范围限制

【数据规模】
1<=N<=250,1<=M<=25000。

提示

【样例说明】
当奶牛们把干草堆放在3-4的边上时，3-4的边的长度相当于从3变到6，约翰的最短路径就变成了1-3-5，总共的距离等于1+7=8，比原来的最短路长度增加了2。

正解
这道题我们可以，先用一个spfa求出d[n]，存起来，再暴力枚举每条边，每条边都*2，然后spfa找d[n]最大值，最后用现在d[n]的最大值-最开始的d[n]

注意：要多提交几遍，可能会被卡掉
AC代码

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,x,y,z,m1,m2,tot,head,tail,d[255],c[255],hd[255],p[50005];
struct stu
{
   
	int w,to,next;	
}a[50005];
void add(int x,int y,int z)//邻接表
{
   
	tot++;
	a[tot].w=z;
	a[tot].to=y;
	a[tot].next=hd[x];
	hd[x]=tot;
}
void spfa()//spfa模板
{
   
	for(int i=2;i<=n;i++)d[i]=2147483647,c[i]=0;
	d[1]=0;c[1]=1;
	head=0;tail=1;
	p[tail]=1;
	while(head<tail)
	{
   
		head++;
		int x1=p[head];
		for(int i=hd[x1];i;i=a[i].next)
		 if(d[x1]+a[i].w<d[a[i].to])
		 {
   
		 	d[a[i].to]=d[x1]+a[i].w;
		 	if(c[a[i].to]==0)
		 	{
   
		 		p[++tail]=a[i].to;
		 		c[a[i].to]=1;
			}
		 }
		c[x1]=0; 
	}
}
int main()
{
   
	freopen("rblock.in","r",stdin);
	freopen("rblock.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
   
		cin>>x>>y>>z;
		add(x,y,z);add(y,x,z);
	}
	spfa();//先跑一遍spfa
	m1=d[n];//存起来
	for(int i=1;i<=m;i++)
	{
   
		a[i*2].w*=2;//边权*2
		a[i*2-1].w*=2;
		spfa();//再跑一遍spfa
		m2=max(m2,d[n]);//找最大
		a[i*2].w/=2;//记得还原
		a[i*2-1].w/=2;
	}
	cout<<m2-m1;
	return 0;
}

下面附本次比赛的其它题目

2020.03.08模拟赛14（第一题）
2020.03.08模拟赛14（第二题）
2020.03.08模拟赛14（第三题）
2020.03.08模拟赛14（第四题）
2020.03.08模拟赛14（总结）

谢谢