比赛 20110725 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 存在与否 最终得分 100
用户昵称 .Xmz 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-25 11:30:35
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <cstdlib>

using namespace std;

const int maxn=1111;
const int oo=10000000;
const int lim=2000000000;

struct edge
{
	int t,c;
	edge *next;
}E[10001],*V[maxn];
int eh,sw[maxn],n,m;
int g[maxn][maxn],w[maxn][maxn];
int d[maxn],ind[maxn];
int f[maxn][3];
int last[maxn],root;
inline void addedge(int a,int b,int c)
{
	E[++eh].next=V[a];  V[a]=E+eh;  V[a]->t=b;  V[a]->c=c;
	E[++eh].next=V[b];  V[b]=E+eh;  V[b]->t=a;  V[b]->c=c;
	ind[a]++;ind[b]++;
}

void dfs(int u)
{
	if (u==root) return ;
	ind[u]--;
	for (edge *e=V[u];e;e=e->next)
	if (ind[e->t])
	{
		g[e->t][++d[e->t]]=u;
		w[e->t][d[e->t]]=e->c;
		if (--ind[e->t]==1)
		{
			last[e->t]=last[u];
			dfs(e->t);
		}
	}
}

void init()
{
	scanf("%d",&n);
	int a,b,c;
	for (int i=1;i<n;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		addedge(a,b,c);
	}
	
	scanf("%d",&m);
	
	for (int i=0;i<=m;i++)
	{
		scanf("%d%d%d",&sw[i],&sw[i+1],&w[sw[i]][1]);
	}
	
	root=V[sw[1]]->t;
	for (int i=1;i<=m;i++)
	{
		last[sw[i]]=sw[i];
		dfs(sw[i]);
	}
}

bool noanswer=false;

void dp(int u)
{
	if (d[u]==0) return;
	for (int i=1;i<=d[u];i++) 
	{	
		dp(g[u][i]);
		if (noanswer) return ;
	}
	int sum=0;int v=0;
	for (int i=1;i<=d[u];i++)
	{
		v=g[u][i];
		if (i<d[u]) sum+=w[last[v]][1];
		sum+=f[v][0];
		if (sum>lim) {noanswer=true;return;}
	}
	
	v=g[u][1];
	f[u][1]=min(oo,sum-f[v][0]+f[v][1]+w[u][1]);
	v=g[u][d[u]];
	f[u][2]=min(oo,sum-f[v][0]+f[v][2]+w[u][d[u]]);
	
	f[u][0]=oo;
	for (int i=1;i<d[u];i++)
	{
		v=g[u][i];int t=g[u][i+1];
		f[u][0]=min( f[u][0],
		sum-f[v][0]-f[t][0]+f[v][2]+f[t][1]+w[u][i]+w[u][i+1]-w[last[v]][1]);
	}
}

void solve()
{
	dp(root);
	if (noanswer || f[root][0]>=oo) printf("-1\n");
	else printf("%d\n",f[root][0]+w[0][1]+w[sw[m]][1]);
}

int main()
{
	freopen("exists.in","r",stdin);
	freopen("exists.out","w",stdout);
	init();
	solve();
	return 0;
}