蓝桥杯历届试题-大臣的旅费 （C++代码）

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream> 
#include<queue>
#define maxn 10010
#include<algorithm>
using namespace std;
int vis[maxn],n;
typedef struct Node{
	int next;
	int dis;
}Node; 
typedef struct Position{
	int pos,sum;
}Position;
vector<Node> graph[maxn]; 
//Position Start,End;
int length=0;
long long money(int dist)
{
    long long sum = 0;
    for(int i=1;i<=dist;i++)
        sum += i+10;
    return sum;
}
int BFS(int s)
{
	int End=1;
	memset(vis,0,sizeof(vis));
	queue<Position> q;
	Position p;
	p.pos=s; p.sum=0;
	vis[s]=1;
	q.push(p);
	while(!q.empty())
	{
		p=q.front(); q.pop();
		int pos=p.pos,sum=p.sum;
		if(sum>length)
		{
			length=sum;
			End=pos;
		}
		for(int i=0;i<graph[pos].size();i++)
		{
			int next = graph[pos][i].next;
			int dis = graph[pos][i].dis;
			if(!vis[next])
			{
				vis[next]=1;
				Position next_position;
				next_position.pos=next;
				next_position.sum=sum+dis; 
				q.push(next_position);
			}
		}
	} 
	return End;
}
int main(void)
{
	cin >> n;
	for(int i=1;i<n;i++)
	{
		int p,q,d;
		cin >> p >> q >> d;
		Node node1,node2;
		node1.next=q;  	node1.dis=d;
		node2.next=p;   node2.dis=d;
		graph[p].push_back(node1);
		graph[q].push_back(node2); 
	}
	int End = BFS(1);
	BFS(End);
	//Start.pos=1; Start.sum=0;
	//End.pos=BFS(1); End.sum=0;
	//BFS(End.pos);
	//printf("%d\n",length);
	printf("%lld",money(length));
	return 0;
}

解题思路:





注意事项:





参考代码: