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

分析：

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

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

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

为什么呢？

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

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

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

还有呢？

注意到数据范围，

$n\le 100$?

不就是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; }

转载于:https://www.cnblogs.com/vercont/p/10210062.html

相关资源：JAVA上百实例源码以及开源项目