玄学问题求教
  • 板块P1395 会议
  • 楼主ZYK_luogu
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/7/30 12:14
  • 上次更新2023/10/23 06:33:58
查看原帖
玄学问题求教
742157
ZYK_luogu楼主2023/7/30 12:14

笑死,这段代码在调试的时候输入的顺序不一样,结果就不一样

#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;
}
2023/7/30 12:14
加载中...