#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int h[100005],e[200005],ne[200005],d[200005],dis[100005],vis[100005],idx,s;
priority_queue<PII,vector<PII> > q;
void add(int x,int y,int z){
//cout<<x<<" "<<y<<" "<<z<<endl;
e[++idx]=y;
ne[idx]=h[x];
h[x]=idx;
d[idx]=z;
}
void dijkstra(){
PII now,nxt;
now.x=dis[1],now.y=1;
q.push(now);
while (!q.empty()){
now=q.top();
q.pop();//cout<<now.y<<endl;
if (vis[now.y])continue;
vis[now.y]=1;
for (int i=h[now.y];i!=-1;i=ne[i]){
if (dis[e[i]]<now.x+d[i]){
dis[e[i]]=now.x+d[i];
nxt.x=dis[e[i]],nxt.y=e[i];
q.push(nxt);
}
}
}
}
int main(){
int n,m,x,y,z;
memset(h,-1,sizeof(h));
cin>>n;
for (int i=1;i<=n;i++){
int k;
cin>>k>>z;
dis[i]=z;
while (cin>>x&&x!=0){
add(x,i,z);
}
}
dijkstra();
cout<<dis[n]<<endl;
return 0;
}
1 个赞