前置芝士：floyd，组合数学
思路
因为要所有点的距离不变，所以我们需要一个全源最短路算法，理所当然的用上了 floyd（下文循环顺序默认为 \(k,i,j\)）。
我们在记录最短路长度的时候，同时记录最短路的数量 \(sum\)。
最后我们枚举所有三个点组成的三元组，如果有 \(i\to k\to j\) 的最短路，且有 \(i\to j\) 的最短路数量正好是 \((i \to k )\times( k \to j)\) 的数量，那么就证明，\(i\to j\) 一定会经过 \(k\)，故 \(k\) 是关键点。
时间复杂度：\(O(n^3)\)。
难点/坑点：注意自已到自己再到其它城市是不可行的，所以要记得在跑完 floyd 后将 \(f_{i,i}=\inf\)。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
using namespace std;
int read() {
int x=0,f=1; char c=getchar();
for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1);
for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }
const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }
#define maxn 205
int n,m;
int f[maxn][maxn],sum[maxn][maxn];
void work() {
in2(n,m);
mem(f,0x3f);
For(i,1,m) {
int u,v,d;
in3(u,v,d);
f[u][v]=f[v][u]=min(f[u][v],d);
sum[u][v]=1;sum[v][u]=1;
}
For(k,1,n) For(i,1,n) For(j,1,n)
if(f[i][k]+f[k][j]<f[i][j])
f[i][j]=f[i][k]+f[k][j],
sum[i][j]=sum[i][k]*sum[k][j];
else if(f[i][j]==f[i][k]+f[k][j])
sum[i][j]+=sum[i][k]*sum[k][j];
int flg=0;
For(i,1,n) f[i][i]=1e9;
For(k,1,n) {
int fin=0;
For(i,1,n){
For(j,1,n)
if(!fin&&f[i][j]==f[i][k]+f[k][j]&&sum[i][j]==sum[i][k]*sum[k][j])
{
cout<<k<<' ';
fin=1;
flg=1; break;
}
if(fin) break;
}
}
if(!flg) return cout<<"No important cities.",void();
}
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
int _=1;
// int _=read();
For(i,1,_) {
work();
}
return 0;
}