分析

a ≠ b的從a到B的最短路，才有重要城市。

求出最短路，才能確定重要城市。

是多源最短路，n ≤ 200，可用Floyd。

若a到b，只有一條最短路，那么 a到b的路徑上的點（除了a、b）都是重要城市，若a到b有多條最短路，某個城市有多條a到b的最短路經過，那么該城市為重要城市。

一邊求最短路，一邊求重要城市：

• result[i][j] = 從i到j的重要城市的二進制表示，用二進制數的每一位對應一個城市，若二進制位為1，該城市是重要城市，若二進制位為0，該城市不是重要城市。
• minDist[i][k] + minDist[k][j] < minDist[i][j]，result[i][j] = (result[i][k] |?result[k][j])，從i到k再從k到j是i到j的最短路，i到k的重要城市和k到j的重要城市都是i到j的重要城市。
• minDist[i][k] + minDist[k][j] == minDist[i][j]，result[i][j] = result[i][j] & (result[i][k] | result[k][j])，此時從i到j有多條最短路，這些最短路共同經過的點是重要城市。

代碼

#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
using namespace std;typedef long long LL;const LL MVal = 1e14;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);LL n, m, u, v, w;cin >> n >> m;vector<vector<LL> > minDist(n + 1, vector<LL> (n + 1, MVal));vector<vector<bitset<210> > > result(n + 1, vector<bitset<210> > (n + 1, 0));for (LL i = 1; i <= m; ++i) {cin >> u >> v >> w;minDist[u][v] = w;minDist[v][u] = w;}for (LL i = 1; i <= n; ++i)  minDist[i][i] = 0;for (LL k = 1; k <= n; ++k) {for (LL i = 1; i <= n; ++i) {for (LL j = 1; j <= n; ++j) {if (i != j && minDist[i][k] + minDist[k][j] < minDist[i][j]) {minDist[i][j] = minDist[i][k] + minDist[k][j];result[i][j] = (result[i][k] | result[k][j]);if (result[i][j] == 0 && result[j][k] == 0)  result[i][j][k - 1] = 1;} else if (i != j && minDist[i][k] + minDist[k][j] == minDist[i][j]) {result[i][j] = (result[i][j] & (result[i][k] | result[k][j]));}}}}bitset<210> res(0);for (LL i = 1; i <= n; ++i) {for (LL j = 1; j <= n; ++j) {if (i != j)  res |= result[i][j];}}if (res == 0)  cout << "No important cities.";else {for (LL i = 0; i < n; ++i)if (res[i] == 1)  cout << (i + 1) << ' ';}return 0;
}

總結

1.多源最短路且邊權不等，且O(n^3)不會TLE，用Floyd。

2.轉化為二進制可減少空間和時間，若數據范圍太大不能用整數表示，可用bitset。