WA54分求助!
查看原帖
WA54分求助!
567522
Yuzilihhh楼主2023/8/26 13:44
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lf long double
#define INF 0x7fffffff
#define debug(alpha) cout<<alpha<<endl
#define min(a,b) (a>b?b:a)
#define max(a,b) (a>b?a:b)
#define Max3(a,b,c) (max(max((a),(b)),(c)))
#define Min3(a,b,c) (min(min((a),(b)),(c)))
using namespace std;
void iread(int &x1145141919810)
{
	x1145141919810=0;
	char c;int wx1145141919810=1;c=getchar();
	while((c>'9'||c<'0')&&c!='-')c=getchar();
	if(c=='-'){wx1145141919810=-1;c=getchar();}
	while(c>='0'&&c<='9'){x1145141919810=x1145141919810*10+c-'0';c=getchar();}
	x1145141919810*=wx1145141919810;
}
int n,x,y,max_depth,max_height,depths[105];
struct node{
	int v,w;
};
bool operator <(node a,node b)
{
	return a.w>b.w;
}
int d[105],dx,dy;
vector<node> graph[105];
bool vis[105];
inline void dfs(int s,int depth)
{
	vis[s]=true;
	++depths[depth];
	max_depth=max(max_depth,depth);
	int l=graph[s].size();
	for(int i=0;i<l;i=-~i)
	{
		if(!vis[graph[s][i].v])
			dfs(graph[s][i].v,depth+1);
	}
	return ;
}
inline void dijkstra(int s)
{
	for(int i=0;i<=n;i=-~i) d[i]=INF;
	d[s]=0;
	priority_queue<node> q;
	q.push({s,0});
	memset(vis,0,sizeof vis);
	while(!q.empty())
	{
		node t=q.top();
		int u=t.v;
		q.pop();
		if(vis[u])
			continue;
		vis[u]=true;
		for(node i:graph[u])
		{
			int v=i.v,w=i.w;
			if(d[v]>d[u]+w)
			{
				d[v]=d[u]+w;
				q.push({v,d[v]});
			}
		}
	}
}
inline void init()
{
	iread(n);
	for(int i=1;i<n;i=-~i)
	{
		iread(x);
		iread(y);
		graph[x].push_back({y,2});
		graph[y].push_back({x,1});
	}
	iread(x);
	iread(y);
}
inline void print()
{
	cout<<max_depth<<endl;
	for(int i=1;i<=max_depth;i=-~i)
		max_height=max(max_height,depths[i]);
	cout<<max_height<<endl<<min(dx,dy);
}
signed main()
{
	init();
	dfs(1,1);
	dijkstra(x);
	dx=d[y];
	dijkstra(y);
	dy=d[x];
	print();
	return 0;
}

错的位置都在答案的第三行,应该是Dijkstra的问题

2023/8/26 13:44
加载中...