武侠梦

Description

按武侠小说的套路，男主一般都会掉下山崖，然后捡到一堆武侠秘籍........

现在小J就遇到了这样的事，他手上拿着一堆武侠秘籍，其中最强的是九阳真经，但问题是学九阳真经前，要先学九阴真经

学九阴真经之前又可以要学一堆的前置技能............

现在给你每个秘籍本身的学习时间，及它们前置技能的相关信息

问你小J至少要花多长的时间才能学会九阳真经，学成之后，他就可以开开心心的去做个扫地僧了

Format

Input

第一行给出N，代表有N种功夫

接下来N行，每行描述一种功夫的相关信息，格式如下

先给出学习这种功夫要花的时间Ti，再给出这种功夫有多少个前置功夫Ki，再给出每个前置功夫的编号

1<=N<=2e5

1<=Ti<=1e9

0<=Ki<i

Output

如题

Samples

输入数据 1

3
3 0
5 1 1
7 1 1      

输出数据 1

10

Hint

先学功夫1，花了3个时间，然后直接学功夫3，花7个时间

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int b[200000],t[200000],a[100000][1000];
int n,m,s;
int f(int x){
	int s=10000000000000000;
	if(b[x]) return b[x];
	if(a[x][0]==0||x==1) return t[x];
	else{
		for(int i=1;i<=a[x][0];i++){
			s = min(s,f(a[x][i])+t[x]);
		}
	}
	b[x] = s;
	return s;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i];
		cin>>a[i][0];
		for(int j=1;j<=a[i][0];j++){
			cin>>a[i][j];
		}
	}
	cout<<f(n);
    return 0;
}

A2

W2

ME 2