CF1482F Useful Edges

问题的难点在于首先要发现这不是多组询问。

首先，显然可以使用 Floyd 算法求出全源最短路。

最暴力的算法枚举边，再枚举每个三元组，时间复杂度为 �(�4)O(n4)。

然后考虑优化，假设我们之前枚举出来的边两端为 �x 和 �y 边长为 �w，并且设其路径为从 �u 到 �x 再从 �y 到 �v。

那么距离就可以表示为：

����,�+�+����,�≤�disu,x​+w+disy,v​≤l

考虑如何优化，我们要统计有用边的个数，因此我们肯定要枚举边，也就是说 �u 和 �v 只能枚举其中一个，才能使时间复杂度为 �(�3)O(n3)。

所以考虑把式子转换一下：

����,�+�≤�−����,�disu,x​+w≤l−disy,v​

那么我们已枚举出了边，再枚举出 �u 就可以得到右边式子结果最大的情况了。

此时记录 ��,�fi,j​ 表示 �v 和 �l 是 �=�u=i 的一个三元组，�j 是 �y 时的最大右边式子的值。

即可轻松得到答案：

cpp

#include<bits/stdc++.h> #define int long long using namespace std; int n,m,dis[605][605],f[605][605],q; struct P{ int u,v,w; }e[400005]; signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; memset(dis,0x3f,sizeof(dis)); for(int i=1;i<=m;i++){ cin>>e[i].u>>e[i].v>>e[i].w; dis[e[i].u][e[i].v]=dis[e[i].v][e[i].u]=e[i].w; } for(int i=1;i<=n;i++)dis[i][i]=0; for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++)dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]); } } cin>>q; for(int i=1,u,v,l;i<=q;i++){ cin>>u>>v>>l; for(int y=1;y<=n;y++)f[u][y]=max(f[u][y],l-dis[y][v]),f[v][y]=max(f[v][y],l-dis[y][u]); } int ans=0; for(int i=1;i<=m;i++){ int x=e[i].u,y=e[i].v,w=e[i].w; for(int u=1;u<=n;u++){ if(dis[u][x]+w<=f[u][y]){ ans++; break;