笑死,这段代码在调试的时候输入的顺序不一样,结果就不一样
#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
#define maxn 50005
struct Node {
int k, step;
Node(int _k, int _step) {
k = _k, step = _step;
}
};
int n, u, v, minv = 1e9, ans = 0;
vector<int> p[maxn];
inline int bfs(int sta, int end) {
printf("bfs(%d, %d)\n", sta, end);
if(sta == end) return 0;
int vis[maxn];
vis[sta] = 1;
queue<Node> Q;
Q.push(Node(sta, 0));
while(!Q.empty()) {
Node cur = Q.front();
Q.pop();
printf("head : k = %d, step = %d\n", cur.k, cur.step);
for(int i = 0; i < p[cur.k].size(); i ++) {
if(!vis[p[cur.k][i]]) {
printf("touch : %d\n", p[cur.k][i]);
vis[p[cur.k][i]] = 1;
Q.push(Node(p[cur.k][i], cur.step + 1));
if(p[cur.k][i] == end) {
return cur.step + 1;
}
}
}
}
return 0;
}
int main() {
cin >> n;
for(int i = 1; i < n; i ++) {
cin >> u >> v;
p[u].push_back(v);
p[v].push_back(u);
}
// 此为调试代码
while(true) {
cin >> u >> v;
cout << bfs(u, v) << endl;
}
for(int i = 1; i <= n; i ++) {
int tot = 0;
for(int j = 1; j <= n; i ++)
tot += bfs(i, j);
if(tot < minv) {
minv = tot;
ans = i;
}
}
cout << ans << " " << minv;
return 0;
}