边表MLE求调
  • 板块学术版
  • 楼主FrozenDream
  • 当前回复11
  • 已保存回复11
  • 发布时间2022/8/17 21:00
  • 上次更新2023/10/27 14:52:36
查看原帖
边表MLE求调
212423
FrozenDream楼主2022/8/17 21:00
#include<bits/stdc++.h>
using namespace std;
int n,u,v,w,tot,nxt[200005],head[200005],to[100005],val[100005],ans,sum2;
void add(int u,int v,int w){
	tot++;
	nxt[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	val[tot]=w;
}
void dfs(int fa,int city,int value){
	ans=max(ans,value);
	for(int i=head[city];i;i=nxt[i]){
		if(to[i]==fa)continue;
		dfs(city,v,value+val[i]);
	}
	return;
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
		sum2+=w;
	}
	dfs(0,1,0);
	cout<<sum2*2-ans;
}

2022/8/17 21:00
加载中...