AT_abc243_e 题解

ikunTLE · 2024-12-25 21:16:43 · 题解

题目传送门

思路

假设我们要删除 u\to v 这条边，若可以删除，必然存在 u\to k\to v 的长度更短。

不难发现，这一点与 Floyd 的思想非常接近。我们可以用 f_{i,j} 统计最短路的基础上，用 g_{i,j} 表示 i\to j 是否有多条最短路。最后统计出每条边是否满足可以删除的条件即可。

时间复杂度 \mathcal{O}(N^3)，可以通过此题。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=3e2+10,M=5e4+10;
int f[N][N];
bool g[N][N];
struct node{
    int u,v,w;
}a[M];
int main(){
    int n=read(),m=read();
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),w=read();
        f[u][v]=f[v][u]=w,a[i]={u,v,w};
    }
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                if(i==j||i==k||k==j)
                    continue;
                if(f[i][j]==f[i][k]+f[k][j])
                    g[i][j]=true;
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j){
                if(i==j||i==k||k==j)
                    continue;
                if(f[i][j]==f[i][k]+f[k][j])
                    g[i][j]=true;
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
    int sum=0;
    for(int i=1;i<=m;++i)
        if(g[a[i].u][a[i].v]||f[a[i].u][a[i].v]!=a[i].w)
            ++sum;
    printf("%d\n",sum);
    return 0;
}