记录编号 280053 评测结果 AAAAAAAAAA
题目名称 圣诞树 最终得分 100
用户昵称 GravatarAntiLeaf 是否通过 通过
代码语言 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;
}