比赛 |
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;
}