蓝桥杯历届试题-大臣的旅费 （C++代码）（时间超限，但是这是一个好的方法）

解题思路:

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define N 10010
#define INT 10000000
using namespace std;

int dist[N][N],sum[N],vis[N],n;
int start=1,last=-1,maxLength=0;
queue<int>q;

int cmp(int a,int b){ return a>b; }

int max(int a,int b)
{
	return a>b?a:b;
}

int money(int dist)
{
	int sum = 0;
	for(int i=1;i<=dist;i++)
		sum += i+10;
	return sum;
}

void BFS(int start)
{
	memset(vis,0,sizeof(vis));
	vis[start]=1;
	while(!q.empty()) q.pop();
	q.push(start);
	while(!q.empty())
	{
		int parent = q.front(); q.pop();
		if(sum[parent]>maxLength) 
		{
			last = parent;
			maxLength = sum[parent];
		}
		for(int son=1;son<=n;son++)
		{
			if(!vis[son] && dist[parent][son]!=0)
			{
				vis[son] = true;
				sum[son] = sum[parent]+dist[parent][son];
				q.push(son);
			}
		}
	}	
}

int main(void)
{
	
	scanf("%d",&n);
	/*
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dist[i][j]=INT;
	*/		
	for(int i=1;i<n;i++)
	{
		int begin,End,s;
		scanf("%d%d%d",&begin,&End,&s);
		if(dist[begin][End]<s || dist[begin][End]==INT) 
			dist[begin][End]=dist[End][begin]=s;
	}
	
	BFS(start);
	sum[last]=0;
	BFS(last);
	
	printf("%d\n",money(maxLength));
}