| ||||||||||
| 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 | |||||||||
1A 哈哈,,贴代码 纪念哈,,#include <cstring>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cmath>
#include <limits>
#include <stdlib.h>
#include <queue>
#include <set>
#include <map>
#include <stack>
#define lson l ,mid ,id << 1
#define rson mid + 1 ,r ,id << 1 | 1
#define maxn 51111
using namespace std;
typedef struct nnn{
int t ,val ,next;
}Edge;
Edge e[maxn*2];
int head[maxn] ,tot ;
bool vis[maxn] ,need[maxn];
int dp[maxn] ,longest[maxn];
void addedge (int a ,int b ,int c){
e[tot].t = b;
e[tot].val = c;
e[tot].next = head[a];
head [a] = tot++;
e[tot].t = a;
e[tot].val = c;
e[tot].next = head[b];
head [b] = tot++;
}
void DP(int s) {
int i ,j ,k , l, temp;
vis[s] = true;
dp[s] = longest[s] = -1;
if (need[s]) dp[s] = longest[s] = 0;
for (k = head[s] ; k != -1 ; k = e[k].next) {
temp = e[k].t;
if (!vis[temp]) {
DP(temp);
if (dp[temp] != -1 && dp[s] == -1) dp[s] = 0;
if (dp[temp] != -1) dp[s] += 2 * e[k].val + dp[temp];
if (longest[temp] != -1) longest[s] = max(longest[s] ,longest[temp] + e[k].val);
}
}
}
int main(){
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
int n ,st ,i ,j ,k ,a ,b ,c;
while (~ scanf ("%d%d",&n ,&st)) {
n --;
memset (head , -1 ,sizeof (head));
memset (need ,0 ,sizeof (need));
memset (vis ,0 ,sizeof (vis));
tot = 0;
while (n --){
scanf ("%d%d%d",&a ,&b ,&c);
addedge(a ,b ,c);
}
scanf ("%d" ,&n);
while (n --) {
scanf ("%d",&a);
need[a] = true;
}
DP (st);
printf ("%d\n",dp[st] - longest[st]);
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator