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