就是vector记录所有能松弛的点，然后枚举i,j判断一下就行。

拜谢大佬，回答请@ , orz

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int n,m,g[N][N];
vector<int> K[N][N];
bool st[N];int cnt;
signed main(){
	scanf("%d%d",&n,&m);
	int u,v,w;
	memset(g,0x3f,sizeof(g));
	while(m--){
		scanf("%d%d%d",&u,&v,&w);
		g[u][v]=g[v][u]=w;
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
				if(g[i][j]>g[i][k]+g[k][j]){
					K[i][j].clear();K[j][i].clear();
					K[i][j].push_back(k);
					K[j][i].push_back(k);
				}
				else if(g[i][j]==g[i][k]+g[k][j]) K[i][j].push_back(k),K[j][i].push_back(k);
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(K[i][j].empty()) continue;
			bool flag=1;int last=-1;
			for(int k:K[i][j])
				if(!(last==-1||k==last)){
					flag=0;break;
					
				}
				else last=k;
			if(flag&&!st[K[i][j][0]]) cnt++,st[K[i][j][0]]=1;
		}
	if(!cnt){
		printf("No important cities.");
		return 0;
	} 
	printf("%d\n",cnt);
    return 0;   
}