Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

1A 哈哈,,贴代码 纪念哈,,

Posted by 20107926LJW at 2012-08-24 21:38:39 on Problem 1935
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator