记录编号	280053	评测结果	AAAAAAAAAA
题目名称	圣诞树	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2016-07-09 20:41:27	内存使用	0.41 MiB

#define MAXC 600UL
#define MAXN 110UL

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

struct Edge{
	int v,nx;
};

Edge edge[MAXN*MAXN];

int ec,n,val[MAXN],Ans,length,headlist[MAXN],dx[MAXN];

bool ex[MAXN];

char inv[MAXC];

queue<int>que;

void Add_Edge(int u,int v){
	edge[++ec].v=v;
	edge[ec].nx=headlist[u];
	headlist[u]=ec;
	return;
}

void spfa(int s){
	memset(dx,0,sizeof(dx));
	dx[s]=val[s];que.push(s);
	while(!que.empty()){
		int p=que.front();que.pop();ex[p]=0;
		for(int i=headlist[p];i;i=edge[i].nx){
			if(dx[edge[i].v]<dx[p]+val[edge[i].v]){
				dx[edge[i].v]=dx[p]+val[edge[i].v];
				if(!ex[edge[i].v]){
					ex[edge[i].v]=1;
					que.push(edge[i].v);
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(dx[i]>Ans){
			Ans=dx[i];
		}
	}
	return;
}

int main(){
    freopen("treez.in","r",stdin);
    freopen("treez.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&val[i]);gets(inv);length=strlen(inv);
		int x=0;
		for(int j=0;j<=length;j++){
			if(inv[j]<'0'||inv[j]>'9'){
				if(x!=0){
					if(x>i){
						Add_Edge(i,x);
					}
					else{
						Add_Edge(x,i);
					}
				}
				x=0;
			}
			else{
				x=(x<<3)+(x<<1)+inv[j]-48;
			}
		}
	}
	for(int i=1;i<=n;i++){
		spfa(i);
	}
	printf("%d",Ans);
	return 0;
}