海洋之心


私信TA

用户名:wanggongsheng

访问量:124499

签 名:

等  级
排  名 17
经  验 20726
参赛次数 3
文章发表 163
年  龄 26
在职情况 学生
学  校
专  业 计算机技术

  自我简介:

读研ing,平时不登录dotcpp

解题思路:

#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));
}


 

0.0分

0 人评分

看不懂代码?想转换其他语言的代码? 或者想问其他问题? 试试问问AI编程助手,随时响应你的问题:

编程语言转换

万能编程问答  

代码解释器

代码纠错

SQL生成与解释

  评论区