大臣的旅费BFS写法

由于本人是先学的是BFS 个人也更喜欢BFS一些
看了一下好像都没有人是BFS写的这题
所以写了一个补充一下

注

个人感觉BFS虽然代码长了一些 但熟练之后写起来比DFS要有套路可循的多

关于本题的思路

本题的思路很清晰
1.任意选一个点u 找到距离最远的v
2.找到距离v最远的x v与x之间的距离即为树的直径即为本题答案

C++ 代码

一下为 BFS写法的详细代码

#include<iostream>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
using namespace std;

const int N=1e5+10;

struct Node
{
    int id,w;   
};

int dist[N];
bool st[N];
vector<struct Node>h[N];

int bfs(int u)
{
    queue<struct Node>q;

    struct Node start;
    start.id=u,start.w=0;

    q.push(start);

    st[u]=true;

    while(q.size())
    {
        struct Node t=q.front();
        q.pop();

        for(int i=0;i<h[t.id].size();i++)
            {
                int &id=h[t.id][i].id;
                int &w=h[t.id][i].w;
                if(st[id]==false)
                {
                    st[id]=true;
                    dist[id]+=w+dist[t.id];
                    struct Node t;
                    t.id=id,t.w=w;
                    q.push(t);
                }
            }

    }

}


int main()
{
    int n;
    scanf("%d",&n);

    for(int i=0;i<n-1;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);

        struct Node tu;
        tu.id=v,tu.w=w;
        h[u].push_back(tu);

        struct Node tv;
        tv.id=u,tv.w=w;
        h[v].push_back(tv);
    }

    bfs(1);

    int mcity=0,mdist=0;

    for(int i=1;i<=n;i++)
        if(mdist<dist[i])
            mdist=dist[i],mcity=i;

    memset(dist,0,sizeof dist);
    memset(st,false,sizeof st);

    bfs(mcity);



    mcity=0,mdist=0;



    for(int i=1;i<=n;i++)
        if(mdist<dist[i])
            mdist=dist[i],mcity=i;

    int s=mdist;

    printf("%lld", s*10 +s*(s + 1ll)/2);

    return 0;
}