思路比较简单： Floyd 预处理每两个点的最短路

然后暴力枚举两个点$i,j$，在枚举中间点$k$ 判断$dis[i][k]+dis[k][j]$是否等于$dis[i][j]$

若等于，那么$i$到$j$的最短路径条数+1

这样来统计最短路径条数

最后，同样的方法，先枚举中转点$c$,枚举两个点$a,b$，判断$a,b$的最短路径是否唯一并且$dis[a][c]+dis[c][b]=dis[a][b]$

#include<bits/stdc++.h>

#define N 205
#define LL long long
using namespace std;

LL d[N][N],n,m,sum[N][N];

int main() {
    scanf("%lld%lld",&n,&m);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) {
            d[i][j]=0x7fffffff;
            if(i==j) d[i][j]=d[j][i]=0;
        }

    for(LL u,v,w,i=1; i<=m; i++) {
        scanf("%lld%lld%lld",&u,&v,&w);
        d[u][v]=min(d[u][v],w);
        d[v][u]=min(d[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(d[i][k]+d[k][j]<d[i][j]) {
                    d[i][j]=d[i][k]+d[k][j];
                }
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++){
            for(int k=1; k<=n; k++) {
                if(d[i][k]+d[k][j]==d[i][j]&&i!=j&&i!=k&&k!=j&&d[i][j]!=0x7fffffff) {
                    sum[i][j]++;
                }
            }
            if(d[i][j]!=0x7fffffff&&!sum[i][j]) sum[i][j]=1;
        }
    /*for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++)
            printf("%d ",sum[i][j]);
        puts("");
    }*/
	
	bool mflg=true;
    for(int c=1; c<=n; c++) {
        bool flg=true;
        for(int a=1; a<=n; a++) {
            for(int b=1; b<=n; b++) {
                if(flg&&d[a][c]+d[c][b]==d[a][b]&&sum[a][b]==1&&a!=b&&a!=c&&b!=c) {
                    flg=false;mflg=false;
                    printf("%d ",c);
                }
            }
        }
    }
	if(mflg) printf("No important cities.");
    return 0;
}