当前位置：首页 > ai >正文

重要的城市（图论最短路）

ai 2025/6/19 6:48:48

分析

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;
}