Loading... [题目链接](https://www.luogu.org/problem/P1841) <!--more--> --- 跑一次floyd即可，新建一个数组c，如果i到j的最短路能被k更新，那么说明最短路一定会经过k，所以c[i][j]保存一下k，如果更新过程发现存在一个相等的更新条件，说明最短路有多条，这个时候就可以删去c[i][j]里面的数. ```cpp #include<bits/stdc++.h> using namespace std; int n, m; int f[209][209], cnt[209][209]; bool ans[209]; int tot; int main(){ scanf("%d%d", &n, &m); memset(f, 0x3f, sizeof(f)); for(int i = 1; i <= n; i++){ f[i][i] = 0; } for(int i = 1; i <= m; i++){ int x, y, w; scanf("%d%d%d", &x, &y, &w); f[x][y] = w; f[y][x] = w; } for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ if(i == k) continue; for(int j = 1; j <= n; j++){ if(i == j || j == k) continue; if(f[i][k] + f[k][j] < f[i][j]){ f[i][j] = f[i][k] + f[k][j]; cnt[i][j] = k; } else if(f[i][k] + f[k][j] == f[i][j]){ cnt[i][j] = 0; } } } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ ans[cnt[i][j]] = 1; } } for(int i = 1; i <= n; i++){ if(ans[i]) printf("%d ", i), tot++; } if(tot == 0) printf("No important cities."); return 0; } ``` Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏