比赛 20110725 评测结果 AAAAWWWWWWWWWWWWWWWW
题目名称 存在与否 最终得分 20
用户昵称 PurpleShadow 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-25 11:41:04
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m,p[N];
int root,dfn;
int PRE;
int st[N],en[N], L[N],R[N],KL[N],KR[N];
int ksum[N];
int dis[N],pw[N];
struct edge
{
	int adv,w;
	edge(const int &_adv,const int &_w):
	adv(_adv),w(_w){}
};
vector<edge> g[N];
inline void addedge(int a,int b,int w)
{
	g[a].push_back(edge(b,w));
}
void dfs(int u)
{
	st[u]=en[u]=u;
	int v,j;
	for (j=0;j<g[u].size();++j)
		{
			v=g[u][j].adv;
			pw[v]=g[u][j].w;
			dis[v]=dis[u]+g[u][j].w;
			dfs(v);
			if (st[u]==u) st[u]=st[v];
			en[u]=en[v];
		}
}
bool comp(const edge &a,const edge &b)
{return st[a.adv]<st[b.adv];}
int dp[N];
void init()
{
	scanf("%d",&n);
	int a,b,w;
	memset(p,0,sizeof(p));
	for (int i=1;i<n;++i)
	{
		scanf("%d%d%d",&a,&b,&w);
		p[a]=b;
		addedge(b,a,w);
	}
	for (root=n;p[root];root=p[root]);
	dfn=0;
	dis[root]=0;
	dfs(root);
	for (int i=1;i<=n;++i)
		sort(g[i].begin(),g[i].end(),comp);
	scanf("%d",&m);
	memset(dp,0x3f,sizeof(dp));
	PRE=0;
	memset(ksum,0,sizeof(ksum));
	memset(KR,0,sizeof(KR));
	int last=0;
	for (int i=0;i<=m;++i)
	{
		scanf("%d%d%d",&a,&b,&w);
		dp[a]=dp[b]=0;
		if (p[a]==p[b]) dp[p[a]]=pw[a]+pw[b];
		if (a==0||b==0) PRE+=w;else
		{
			L[b]=a;R[a]=b;
			KL[b]=w;KR[a]=w;
			for (int j=last+1;j<=a;++j)
				ksum[j]=ksum[j-1]+KR[j];
			last=a;
		}
	}
}
inline int Ksum(int l,int r)
{return ksum[r]-ksum[l];}
void Getdp(int u)
{
	int c1,c2,j;
	int p1,p2;
	int weight;
	int s1=0,s2=0;
	for (j=0;j<g[u].size();++j)
		Getdp(g[u][j].adv);
	for (j=2;j<g[u].size();++j)
		s2+=dp[g[u][j].adv];
	for (j=2;j<g[u].size();++j)
	{
		c1=g[u][j-2].adv;c2=g[u][j-1].adv;
		weight=KR[st[c1]]+KL[en[c2]];
		p1=p[st[c1]];p2=p[en[c2]];
		weight+=Ksum(st[p1],en[p1])+Ksum(st[p2],en[p2]);
		weight+=dis[en[p1]]+dis[en[p2]]-2*dis[u];
		dp[u]=min(dp[u],weight+s2+s1);
		s2-=dp[g[u][j].adv];
		s1+=dp[g[u][j-2].adv];
	}
}
void slove()
{
	Getdp(root);
	printf("%d\n",dp[root]==0x3f3f3f3f?-1:dp[root]+PRE);
}
int main()
{
freopen("exists.in","r",stdin);
freopen("exists.out","w",stdout);
	init();
	slove();
	return 0;
}