蓝桥杯 历届试题 大臣的旅费 https://i.cnblogs.com/EditPosts.aspx?opt=1

使用邻接表一直超时   改用vector秒过31ms    不怎么了解vector的运行原理  只会简单的应用    两次dfs直接解决

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<math.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define N 10006
vector<int>Q[N];
int w[N],dis[N],n,k,maxx=0;
void q(int s,int sum)
{
    if(sum>maxx)
    {
        maxx=sum;
        k=s;
    }
    for(int i=0;i<Q[s].size();i+=2)
    {
        int f=Q[s][i];
        if(!w[f])
        {
            w[f]=1;
            q(f,sum+Q[s][i+1]);
        }
    }
}
int main()
{
    scanf("%d",&n);
    int e,f,g;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&e,&f,&g);
        Q[e].push_back(f);
        Q[e].push_back(g);
        Q[f].push_back(e);
        Q[f].push_back(g);
    }
    maxx=0;
    memset(w,0,sizeof(w));w[1]=1;
    q(1,0);
    maxx=0;
    memset(w,0,sizeof(w));w[k]=1;
    q(k,0);
    printf("%d
",maxx*10+(maxx+1)*maxx/2);
    return 0;
}