P3884 18分求调
查看原帖
P3884 18分求调
740948
rb_tree楼主2024/7/25 11:35
#include<cstdio>
#include<algorithm>
#include<queue>
#include<utility>
using namespace std;
inline void write(int x) 
{
    if(x<0) 
    { 
        x=-x;
        putchar('-');
    }
    if(x>9) write(x/10);
    putchar((x%10)^48);
}
inline int read()
{
    int x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'||ch>='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*w;
}
int to[205],h[205],nxt[205],dis[205],cnt,n,maxdeepth,maxwideth;
bool vis[205],vis1[205],vis2[205];
inline void addedge(int a,int b)
{
    to[++cnt]=b;
    nxt[cnt]=h[a];
    h[a]=cnt;
    return;
}
struct statu
{
    int x,step;
};
inline void dfs(int x,int deepth)
{
    maxdeepth=max(deepth,maxdeepth);
    for(int i=h[x];i;i=nxt[i])
    {
        int v=to[i];
        if(vis1[v]==0)
        {
            vis1[v]=1;
            dfs(v,deepth+1);
            vis1[v]=0;
        }
    }
}
inline void bfs()
{
    queue<statu> q;
    statu ttmp;
    ttmp.step=0;
    ttmp.x=1;
    q.push(ttmp);
    while(!q.empty())
    {
        int x=q.front().x,step=q.front().step+1;
        maxwideth=max(maxwideth,int(q.size()));
        q.pop();
        for(int i=h[x];i;i=nxt[i])
        {
            int v=to[i];
            if(vis2[v]==0)
            {
                vis2[v]=1;
                statu tmp;
                tmp.x=v;
                tmp.step=step;
                q.push(tmp);
            }
        }
    }
}
inline void dijkstra(int s)
{
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    fill(dis+1,dis+n+1,0x3fffffff);
    q.push(make_pair(0,s));
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(vis[u]==1) continue;
        vis[u]=1;
        for(int j=h[u];j;j=nxt[j])
        {
            int v=to[j];
            if(vis[v]==0&&dis[u]+1<dis[v])
            {
                if(v>u) dis[v]=(dis[u]+1)<<1;
                if(v<u) dis[v]=(dis[u]+1);
                q.push(make_pair(dis[v],v));
            }
        }
    }
    return;
}
int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        addedge(u,v);
        addedge(v,u);
    }
    dfs(1,0);
    bfs();
    write(maxdeepth-1);
    putchar('\n');
    write(maxwideth-1);
    putchar('\n');
    int x=read(),y=read();
    dijkstra(x);
    write((dis[y]>>1)-1);
	return 0;
}
2024/7/25 11:35
加载中...