[汗]我不就只写了一个dfs+dijkstra吗?为啥没人调
by Yuzilihhh @ 2023-08-26 17:55:44
dijkstra写得没问题,但是只需要输出dy就可以了
AC代码:
```cpp
#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<<dy;
}
signed main()
{
init();
dfs(1,1);
dijkstra(y);
dy=d[x];
print();
return 0;
}
by Null_h @ 2023-08-26 17:58:39