算法
(BFS) $O(N^2)$
注意到 $N$ 比较小,所以我们直接跑 $N$ 遍 BFS
即可。
最短路:
假设 $N \leqslant M$
- BFS $O(M)$ 边权都为 $1$
- Dijkstra $O(M\log M)$ 边权都为正边
- Floyd $O(N^3)$ 实现简单
- Bellman-ford $O(NM)$ 含有负边
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::queue;
const int INF = 1001001001;
int main() {
int n, x, y;
cin >> n >> x >> y;
--x; --y;
vector<int> ans(n);
rep(sv, n) {
vector<int> dist(n, INF);
queue<int> q;
auto push = [&](int v, int d) {
if (dist[v] != INF) return;
dist[v] = d;
q.push(v);
};
push(sv, 0);
while (!q.empty()) {
int v = q.front(); q.pop();
int d = dist[v];
if (v - 1 >= 0) push(v - 1, d + 1);
if (v + 1 < n) push(v + 1, d + 1);
if (v == x) push(y, d + 1);
if (v == y) push(x, d + 1);
}
rep(i, n) ans[dist[i]]++;
}
rep(i, n) ans[i] /= 2;
for (int i = 1; i <= n - 1; ++i) {
cout << ans[i] << '\n';
}
return 0;
}
这个是重载个函数吗?
不是,这是lambda表达式
噢噢,好的