问题标题: 已AC，送豆！！！

@董子墨 @刘皓宇 @芮奥运

6179 10分！！！

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
int n,m,x,y,z,f[55][55],dis[55],s[55][55],k[55][55],ans,ss[55][55]; 
bool no[55][55];
int main(){
	memset(f,0x3f,sizeof(f));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		f[x][y]=f[y][x]=k[x][y]=k[y][x]=z;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(f[i][k]+f[k][j]<1000000)ss[i][j]++;
				if(f[i][k]+f[k][j]<f[i][j]){
					f[i][j]=f[i][k]+f[k][j];
					no[i][j]=0;
					s[i][j]=k;
				}
				if(f[i][k]+f[k][j]==f[i][j]){
					no[i][j]=1;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(k[i][j]!=0)ss[i][j]++;
			if(ss[i][j]>1&&no[i][j]==0&&dis[s[i][j]]==0){
				dis[s[i][j]]=1;
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}

快！！！

包涵宇在2021-03-23 21:09:41追加了内容

@董子墨 

40分！

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
int n,m,f[55][55],tf[55][55],s;
struct node{
	int x,y,z;
}a[10005];
int main(){
	memset(f,0x3f,sizeof(f));
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y>>a[i].z;
		f[a[i].x][a[i].y]=a[i].z;
		f[a[i].y][a[i].x]=a[i].z;
	}
	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]);
	for(int l=1;l<=n;l++){
		memset(tf,0x3f,sizeof(tf));
		for(int i=1;i<=m;i++){
			if(a[i].x!=l&&a[i].y!=l){
				tf[a[i].x][a[i].y]=a[i].z;
				tf[a[i].y][a[i].x]=a[i].z;
			}
		}
		for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)tf[i][j]=min(tf[i][j],tf[i][k]+tf[k][j]);
		int ff=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++)
				if(tf[i][j]<100000000&&tf[i][j]!=f[i][j]){
					ff=1;
					break;
				}
			if(ff==1)break;
		}
			
		s+=ff;
	}
	cout<<s;
	return 0;
}

HELP！！！

包涵宇在2021-03-25 16:03:39追加了内容

送豆啦！！！