就是在跑 Floyd 的时候记录当前最小值是在哪个中转点取到的，记为 $g[i][j]$。

然后如果用别的中转点又跑到了一样的长度就把原来那个删了。

最后去重就行。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
multiset<int> ans;
set<int> s;
int n, m, f[N][N], INF = 1e9, g[N][N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            f[i][j] = INF;
        }
        f[i][i] = 0;
    }
    while(m --){
        int u, v, w;
        cin >> u >> v >> w;
        f[u][v] = f[v][u] = w;
    }
    for(int k = 1; k <= n; k ++){
        for(int i = 1; i <= n; i ++){
            if(i == k)continue;
            for(int j = i; j <= n; j ++){
                if(j == k || j == i)continue;
                if(f[i][j] > f[i][k] + f[k][j]){
                    f[j][i] = f[i][j] = f[i][k] + f[k][j];
                    if(ans.find(g[i][j]) != ans.end() && g[i][j] != 0)ans.erase(ans.find(g[i][j]));
                    g[i][j] = g[j][i] = k;                   
                    ans.insert(k);
                }else if(f[i][j] == f[i][k] + f[k][j] && ans.find(g[i][j]) != ans.end() && g[i][j] != 0){
                    ans.erase(ans.find(g[i][j]));
                    g[i][j] = g[j][i] = 0;
                }
            }
        }
    }
    for(auto i : ans){
        s.insert(i);
    }
    if(s.size() == 0){
        cout << "No important cities.";
    }else for(auto j : s){
        cout << j << ' ';
    }
    return 0;
}

值得注意的是不能重复遍历，不然就全删完了。 还有用完 multiset 还要再去一遍重，不然会全 WA。