9 10 过不了???
查看原帖
9 10 过不了???
866969
telankesi楼主2023/4/16 21:37
#include <stdio.h>
#include <string.h>
#include <math.h>
int n;
int g[10002][10002];//路径距离
int b[1000000];//每一个路径下,同层的宽度
int min(int x, int y) {
	return x < y ? x : y;
}
int main() {
	scanf("%d", &n);
	int x, y;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			if (i != j)
				g[i][j] = 1e9;
	}
	for (int i = 1; i <= n-1; i++) {
		
		scanf("%d %d", &x, &y);
		g[x][y] = g[y][x] = 1;
		
	}

	scanf("%d %d", &x, &y);
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			if (k == i)continue;
			for (int j = 1; j <= n; j++) {
			
		g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}
	int r;//路径
	if (g[x][1] + g[1][y] == g[x][y])r = g[x][1] * 2 + g[1][y];
	else if (x < y)r = g[x][y];
	else r = g[x][y] * 2;
	int h=0;//深度
	int l=0;//宽度
	
	for (int i = 1; i <= n; i++) {
		if (h < g[1][i]+1)h = g[1][i] + 1;
		b[g[1][i]]++;
	}
	for (int i = 0; i <=h ; i++) {
		if (l < b[i] )l = b[i] ;
	}
	
	printf("%d\n%d\n%d", h, l, r);
	return 0;
}
2023/4/16 21:37
加载中...