我的做法比较抽象，先跑全源最短路，再从每个点 $rt_i$ 出发 dfs，如果一条边 $(u,v,w)$ 满足 $dis_{rt_i,u}+w=dis_{rt_i,v}$，就把这条边加入新图。每次跑完就求割边打标记。

是我的代码写错了，还是做法就是错的？

Code:

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned ll
#define ldb long db
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<db,db>
#define F first
#define S second
#define pb push_back
#define mp make_pair
using namespace std;
const int N=305,M=9e4+5;
int n,m,a,b,id[N][N],ans,dfn[N],low[N],siz;
ll c,f[N][N],dis[N][N];
bool book[M],vis[N];
vector<int> e[N];
void chmin(int &x,int y){
	if(x>y) x=y;
}
void dfs(int cur,int frm){
	if(vis[cur]) return;
	vis[cur]=1;
	for(int i=1;i<=n;++i) if(i!=cur && dis[frm][cur]+f[cur][i]==dis[frm][i]){
		e[cur].pb(i);
		e[i].pb(cur);
		dfs(i,frm);
	}
}
void tarjan(int cur,int fa){
	dfn[cur]=low[cur]=++siz;
	for(int to:e[cur]) if(to!=fa){
		if(!dfn[to]){
			tarjan(to,cur);
			chmin(low[cur],low[to]);
			if(dfn[cur]<low[to]) book[id[cur][to]]=1;
		}
		else chmin(low[cur],dfn[to]);
	}
}
int main(){
	memset(dis,0x3f,sizeof dis);
	memset(f,0x3f,sizeof f);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) dis[i][i]=0;
	for(int i=1;i<=m;++i){
		scanf("%d%d%lld",&a,&b,&c);
		id[a][b]=id[b][a]=i;
		f[a][b]=f[b][a]=c;
		dis[a][b]=dis[b][a]=c;
	}
	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][j],dis[i][k]+dis[k][j]);
	for(int i=1;i<=n;++i){
		memset(dfn,0,sizeof dfn);
		memset(low,0,sizeof low);
		memset(vis,0,sizeof vis);
		siz=0;
		for(int j=1;j<=n;++j) e[j].clear();
		dfs(i,i);
		tarjan(i,0);
	}
	for(int i=1;i<=m;++i) if(!book[i]) ++ans;
	printf("%d",ans);
	return 0;
}
//Arcana.