首页 > 代码库 > 清北 游
清北 游
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #include<cmath> #include<queue> #include<vector> #include<climits> #include<string> #include<cstdlib> #include<ctime> #define MAX 1000000007 #define LL long long using namespace std; int tot,num[150005],power[150005],nxt[150005],head[150005],n,ans,all,dep[150005],vis[150005],d; void add(int p1,int p2,int wi) { tot++; num[tot]=p2; power[tot]=wi; nxt[tot]=head[p1]; head[p1]=tot; } void dfs(int now,int z) { int i,p=0; for(i=head[now];i;i=nxt[i]) { if(!vis[num[i]]) { p=1; vis[num[i]]=1; dfs(num[i],z+power[i]); } } if(p==0) { d=max(d,z); return; } } int main() { int s,t,w,i; scanf("%d",&n); for(i=1;i<=n-1;i++) { scanf("%d%d%d",&s,&t,&w); add(s,t,w); add(t,s,w); all+=w; } all=all*2; vis[1]=1; dfs(1,0); ans=all-d; printf("%d",ans); return 0; }
很容易分析得,最短=2*总和-最长链
清北 游
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。