题目描述
代码给了很详细的步骤,希望能帮到你
样例
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
//关键步骤
//1.选择一个结点开始遍历,找到最远的结点u
//2.再从u开始遍历第二次,找到最远结点走过的长度就是答案
int n;
struct node{
int id,length;//记录该点能到达的位置和下个点的距离
};
vector<node>h[100003];
int dist[100003];
void dfs(int u,int father,int distance){
dist[u]=distance;//记录当前结点走过的长度
for(auto i:h[u]){//遍历h[i]结点
if(i.id!=father){//下一个能走的结点不是父节点(也就是不能往回走)
dfs(i.id,u,distance+i.length);//dfs下一个结点
}
}
}
int main(){
cin>>n;
for(int i=0;i<n-1;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
h[a].push_back({b,c});//a能到达的下一个位置和长度
h[b].push_back({a,c});//b能到达的下一个位置和长度
}
dfs(1,-1,0);//从第一个点开始遍历,-1是第一个点的父亲结点,0是目前走过的距离
int u=1;
for(int i=1;i<=n;i++){//遍历n个结点,找到走过路径最长结点的下标
if(dist[i]>dist[u]){
u=i;
}
}
dfs(u,-1,0);//u是走过最远的结点,从u开始遍历第二次,找到最远结点走过的长度就是最终答案啦
for(int i=1;i<=n;i++){
if(dist[i]>dist[u]){
u=i;
}
}
int s=dist[u];
long long int ans=0;
for(int i=1;i<=s;i++){//求出走s这么长的路需要的路费
ans+=10+i;
}
cout<<ans;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla