AT_abc243_e 题解

思路

假设我们要删除

u\to v

这条边，若可以删除，必然存在

u\to k\to v

的长度更短。

不难发现，这一点与 Floyd 的思想非常接近。我们可以用

f_{i,j}

统计最短路的基础上，用

g_{i,j}

表示

i\to j

是否有多条最短路。最后统计出每条边是否满足可以删除的条件即可。

时间复杂度

\mathcal{O}(N^3)

，可以通过此题。

AC CODE

CPP

#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;
}

文章操作

思路

相关推荐

评论

AT_abc243_e 题解