大臣的旅费

做了一道图论题，分享一下自己的理解

大臣的旅费

第四届蓝桥杯省赛C++A组，贴一份链接(1207. 大臣的旅费 - AcWing题库)

这是一个图论题，可以通过dfs，直接解出来，深搜遍历每个点，并且更新最远的距离。

同时这个题用到了树的直径，感兴趣的同学可以去搜一下，这里直接给出结论，在第一次搜索中，找到最远的距离的点，以这个点为起点，再搜一遍，得到的最远的距离，就是树的最大直径。

#include<iostream>
#include<cstring>

typedef long long ll;

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 20;
// 链式前向星 这里因为是无向图，所以一个数据存两份
int h[N], e[M], ne[M], idx, n;
// far记录最远的距离，w存经过每个路的距离
int far, w[M];
// cnt记录答案，开long long 防止爆
ll cnt;
// 因为每个城市只走一遍，记录一下
int st[M];
// 向前星存图
void add(int a,int b,int c)
{
    e[idx] = b,ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}
// dfs搜索，同时用st记录，防止 tle
void dfs(int u,int dis)
{
    st[u] = 1;
    // 更新 cnt 和 far
    if(dis > cnt)
    {
        cnt = dis;
        far = u;
    }
    // 遍历
    for(int i = h[u];i != -1;i = ne[i])
    {
        int j = e[i];
        if(!st[j])
            dfs(j,dis + w[i]);
    }
}

void solve()
{
    // 链表头节点初始化
    memset(h,-1,sizeof h);

    cin >> n;
	// 读入数据
    for(int i = 0;i < n - 1;i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    // 搜索第一次
    dfs(1,0);
    // 初始化st
    memset(st,0,sizeof st);
    // 用树的最大直径，来搜索第二次
    dfs(far,0);
    // 输出答案
    cout << cnt * 10 + (cnt + 1) * cnt / 2;
}

int main()
{
    solve();
    return 0;
}