AcWing 1207. 大臣的旅费
原题链接
中等
作者:
让我AC吧球球了
,
2022-02-15 23:14:34
,
所有人可见
,
阅读 157
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
const int N = 100010;
int n;
struct edge{
int id,w;
};
vector<edge> h[N];
int dist[N];
void dfs(int u,int father, int distance){
dist[u] = distance;
for(vector<edge>::iterator it=h[u].begin();it != h[u].end();it++) //y总用的auto node : h[u] 蓝桥杯运行不过
//所以换成迭代器
if((*it).id != father){
dfs((*it).id,u,distance+(*it).w);
}
}
int main(){
scanf("%d",&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});
h[b].push_back({a,c});
}
dfs(1,-1,0);
int u = 1;
for(int i=1;i<=n;i++){
if(dist[i] >dist[u])
u=i;
}
dfs(u,-1,0);
for(int i=1;i<=n;i++){
if(dist[i]>dist[u]){
u = i;
}
}
int s = dist[u];
printf("%lld",10*s + (s + 1ll) * s / 2);
return 0;
}