牛客OI賽制測試賽 D：小葉的巡查

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<LL,int> P;
const int maxn=30000+100;
const LL INF=1e18;

LL dis[maxn];
bool vis[maxn];
struct Edge{
  
  int to,next;
  LL len;
}edge[maxn<<1];
int head[maxn],tot;
int n,node;

void Dijkstra(int s){
  
  priority_queue<P,vector<P>,greater<P> >que;
  for(int i=1;i<=n;i++) dis[i]=INF,vis[i]=false;
  dis[s]=0;
  node=s;
  que.push(P(0,s));
  while(!que.empty()){
    
    P p=que.top();
    que.pop();
    int u=p.second;
    if(vis[u]) continue;
    vis[u]=true;
    for(int i=head[u];i!=-1;i=edge[i].next){
      
      Edge e=edge[i];
      int v=edge[i].to;
      if(!vis[v] && dis[v]>dis[u]+e.len){
        
        dis[v]=dis[u]+e.len;
        que.push(P(dis[v],v));
        if(dis[v]>dis[node]) node=v;
      }
    }
  }
}

int main(){
  
  scanf("%d",&n);
  tot=0;
  for(int i=1;i<=n;i++) head[i]=-1;
  for(int i=1;i<n;i++){
    
    int u,v;
    LL len;
    scanf("%d%d%lld",&u,&v,&len);
    edge[tot].to=v;
    edge[tot].len=len;
    edge[tot].next=head[u];
    head[u]=tot++;
    edge[tot].to=u;
    edge[tot].len=len;
    edge[tot].next=head[v];
    head[v]=tot++;
  }
  Dijkstra(1);
  Dijkstra(node);
  printf("%lld\n",dis[node]*10+(1+dis[node])*dis[node]/2);
}