题目:https://www.luogu.org/problemnew/show/P3905

分析:

此题是显然的最短路算法,只是看到一起删掉的一堆边感到十分棘手,而且还要求出的是最短添加边的总长度

但如果仔细观察就可以发现,我们其实并不用一个一个的全部枚举,只需要把添加的边做最短路就行了。

我们可以首先把数组初始化为一个较大的数,然后每读入一条边,就把此边的权值记录,但还要把它清零。

为什么呢?

因为我们清零相当于不考虑此边的权值,但又可以经过这条边,有效的能保留下删去的边,来仅仅考虑被删边的最短路。

然后读入删掉的边,这时候我们把那些删去的边赋上原来的权值,进行计算即可。

what?这不就是最短路模板吗?

还有呢?

注意到数据范围,

n≤100n\leq100n100?

不就是Floyd常见的数据范围吗?

于是floyd都往上套了。。。

于是此题经过转换,就成为了一个可用Floyd,dijkstra,spfa等多种最短路算法解决的板子题了。。。

下面给出Floyd代码:

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int f[105][105],g[105][105];
int main()
{
	
	int n,m;
	scanf("%d%d",&n,&m);
	memset(f,0x3f3f3f3f,sizeof(f));
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		g[x][y]=g[y][x]=z;
		f[x][y]=f[y][x]=0;
	}
	int d;
	scanf("%d",&d);
	for(int i=1;i<=d;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		f[x][y]=f[y][x]=g[x][y];
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				f[i][j]=fmin(f[i][j],f[i][k]+f[k][j]);
			}
		}
	}
	int x,y;
	scanf("%d%d",&x,&y);
	printf("%d",f[x][y]);
	return 0;
}