题解：AT_abc243_e [ABC243E] Edge Deletion

· · 题解

其实不难。

首先，简单地判断需要删去的边满足的条件：

将第 i 条边两端点记作 a_i, b_i，边权为 c_i，当 a_i 到 b_i 的路径中存在小于 c_i 的情况（可以发现这条路径不是第 i 条边），一定能删除该边，因为任何经过该边的路径中必须经过这两个端点，而这两个端点又有更短的路径，因此这条路径一定不是最短路。

当路径中存在有长度不等于 1 的路径等于 c_i 的情况，也能删除该边，同理。

其次，基于原图删边，要是每次删边后都符合要求，删边是否有冲突？

不会，因为任意两点间的最短路在删边前后不变，满足【条件】的依然满足，否则还是不满足。

剩下的边都是被保留的边，因为他们至少会被自己使用。

因此得解，用 floyd 预处理两点间的最短路，然后对于每条边判断是否能删，也就是是否有长度不为 1 的路径小于或等于该边。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=305,maxm=1e5+5,inf=1e18;
int n,m,u[maxm],v[maxm],w[maxm],f[maxn][maxn],unused;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=inf;// 避免特判，当 i=j 时也取 inf
        }
    }
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[i];
        f[u[i]][v[i]]=w[i];
        f[v[i]][u[i]]=w[i];
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++){
        int a=u[i],b=v[i],c=w[i];
        unused=0;
        for(int j=1;j<=n;j++){
            if(f[a][j]+f[j][b]<=c){
                unused=1;// 因为 i=j 时取了 inf，所以这句话的用意在判断长度至少为 2 的边
                break;
            }
        }
        ans+=unused;
    }
    cout<<ans;
    return 0;
}