1 条题解
-
0
小孩亲笔:
#include<bits/stdc++.h> using namespace std; typedef long long LL; struct node { int x,y,next;LL d; }a[410000];int len,last[210000]; void ins(int x,int y,LL d) { len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len; } LL far;int t; void findfar(int x,int fa,LL d) { if(d>far) far=d,t=x; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fa) findfar(y,x,d+a[k].d); } } bool bk; LL d1[210000],d2[210000]; void findd(int x,int fa,int t) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fa) { if(t==1) d1[y]=d1[x]+a[k].d; else d2[y]=d2[x]+a[k].d; findd(y,x,t); } } } int main() { int n,m; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { int x,y;LL d; scanf("%d%d%lld",&x,&y,&d); ins(x,y,d);ins(y,x,d); } far=0;findfar(1,0,0); int t1=t; far=0;findfar(t1,0,0); int t2=t; findd(t1,0,1); findd(t2,0,2); LL ans=0; for(int i=1;i<=n;i++) ans=max(ans,min(d1[i],d2[i])); printf("%lld\n",ans+far); return 0; }
- 1
信息
- ID
- 1509
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 21
- 已通过
- 9
- 上传者