比赛 |
20110725 |
评测结果 |
AWWWAWWAAAWAAAAAWWAA |
题目名称 |
存在与否 |
最终得分 |
60 |
用户昵称 |
苏轼 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-07-25 12:56:16 |
显示代码纯文本
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long s64;
const int MAXN=1005;
const s64 oo=~0u>>1;
#define pb push_back
#define mp make_pair
typedef pair<int,int> Pair;
typedef vector<Pair>::iterator Ptr;
vector<Pair> adj[MAXN];
inline void addedge(int u,int v,int w)
{
adj[u].pb(mp(v,w));
adj[v].pb(mp(u,w));
}
int L[MAXN],R[MAXN];
inline bool cmp(const Pair &u,const Pair &v)
{
return L[u.first]<L[v.first];
}
int to[MAXN],father[MAXN];
void dfs(int u)
{
if (to[u]!=0)
{
L[u]=to[u];
R[u]=to[u];
}
else
{
int v;
for(Ptr it=adj[u].begin();it!=adj[u].end();)
if ((v=it->first)!=father[u])
{
father[v]=u;
dfs(v);
it++;
}
else
it=adj[u].erase(it);
sort(adj[u].begin(),adj[u].end(),cmp);
L[u]=L[adj[u].front().first];
R[u]=R[adj[u].back().first];
}
}
int sum[MAXN];
s64 d[MAXN][3];
void dp(int u)
{
if (to[u]!=0)
d[u][0]=d[u][1]=d[u][2]=0;
else
{
int v;
s64 sigma=0;
for(Ptr it=adj[u].begin();it!=adj[u].end();it++)
if ((v=it->first)!=father[u])
{
dp(v);
sigma+=d[v][0];
}
d[u][0]=oo;
int k,j=adj[u].front().first;
s64 tj=d[j][1]-d[j][0]+adj[u].front().second+sum[R[j]];
s64 t;
for(Ptr it=++adj[u].begin();it!=adj[u].end();it++)
if ((k=it->first)!=father[u])
{
s64 tk=d[k][2]-d[k][0]+it->second-sum[L[k]];
if ((t=sigma+tk+tj)<d[u][0])
d[u][0]=t;
tj=d[k][1]-d[k][0]+it->second+sum[R[k]];
j=k;
}
v=adj[u].back().first;
d[u][1]=sigma-d[v][0]+d[v][1]-(sum[R[u]]-sum[R[v]])+adj[u].back().second;
v=adj[u].front().first;
d[u][2]=sigma-d[v][0]+d[v][2]-(sum[L[v]]-sum[L[u]])+adj[u].front().second;
}
}
int N,M;
int main()
{
freopen("exists.in","r",stdin);
freopen("exists.out","w",stdout);
scanf("%d",&N);
int tot=0;
for(int i=0;i<N-1;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);
tot+=w;
}
scanf("%d",&M);
for(int i=1;i<M+2;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
to[v]=i;
sum[i]=sum[i-1]+w;
tot+=w;
}
dfs(1);
dp(1);
if (d[1][0]>tot)
printf("-1\n");
else
printf("%d\n",(int)(d[1][0]+sum[M+1]));
return 0;
}