| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
900题留念#include<iostream>
#include<stdio.h>
#include<vector>
#include<limits.h>
#include<string.h>
using namespace std;
const int N = 50010;
struct E{
int v,w,next;
}elist[N<<1];
int head[N];
int e_cnt;
int n,k;
int city[N];
int dp[N][2]; // 0 not coming back, 1 coming back
void addedge(int a,int b,int c){
elist[e_cnt].v = b;
elist[e_cnt].w = c;
elist[e_cnt].next = head[a];
head[a] = e_cnt++;
}
void dfs(int u,int f){
dp[u][0] = dp[u][1] = 0;
int m = 0;
for(int i=head[u];i!=-1;i=elist[i].next){
int v = elist[i].v;
int w = elist[i].w;
if(v==f)continue;
dfs(v,u);
if(!dp[v][1] && !city[v]) continue;
dp[u][0] += 2*w+dp[v][1];
dp[u][1] += 2*w+dp[v][1];
m = max(m,w+dp[v][1]-dp[v][0]);
}
dp[u][0] -= m;
}
int main()
{
int a,b,c;
scanf("%d%d",&n,&k);
e_cnt = 0;
memset(head,-1,sizeof head);
for(int i=0;i<n-1;i++){
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
int cnt,x;
scanf("%d",&cnt);
while(cnt--){
scanf("%d",&x);
city[x] =1;
}
dfs(k,0);
printf("%d\n",min(dp[k][0],dp[k][1]));
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator