黄山seo公司,seo基础知识包括什么,响应式网站首页,wordpress 新建文件权限分析
a ≠ b的从a到B的最短路#xff0c;才有重要城市。
求出最短路#xff0c;才能确定重要城市。
是多源最短路#xff0c;n ≤ 200#xff0c;可用Floyd。
若a到b#xff0c;只有一条最短路#xff0c;那么 a到b的路径上的点#xff08;除了a、b#xff09;都是…
分析
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;vectorvectorLL minDist(n 1, vectorLL (n 1, MVal));vectorvectorbitset210 result(n 1, vectorbitset210 (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]));}}}}bitset210 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。
