蓝桥杯2013年第四届真题-大臣的旅费 （C++代码）听说这道题有点难？

解题思路:就是一个图边的搜素，只需要搜到最长的，再从最长搜到最短就可以

注意事项:这个题不能来数组来解吧，反正我把所有数组都开了一遍；最后用了vector

参考代码:

#include<iostream>
#include<vector>
#include<cstring> 
#define N 1000000
using namespace std;
vector<int>a[N];
vector<int>b[N];
bool p[N];
int l,ans=0,n;
void dfs(int x,int sum)
{
 if(sum>ans)
 {
  ans=sum;
  l=x;
  }
 p[x]=true;
 for(int i=0;i<a[x].size();i++)
 {
  if(p[a[x][i]]) continue;
  sum+=b[x][i];
 
  dfs(a[x][i],sum);
  sum-=b[x][i];
 }
 p[x]=false;
}
int main()
{
  cin>>n;
  for(int i=1;i<n;i++)
  {
   int tx,ty,ts;
   cin>>tx>>ty>>ts;
   a[tx].push_back(ty);
   b[tx].push_back(ts);
   
   a[ty].push_back(tx);
   b[ty].push_back(ts);
  }
  dfs(1,0);
  memset(p,false,sizeof(p));
  dfs(l,0);
  int s=0;
  for(int i=1;i<=ans;i++)
      s+=i+10;
      cout<<s;
}