官方题解

题目大意

有 $n$ 个技能，学习每个技能需要花费 $t_i$ 时间，在学习每个技能之前，需要已学习若干个前置技能，需要求出学习第 $n$ 个技能的最小花费。

解题思路

可以使用队列存储需要学习的技能，最初存入第 $n$ 个技能，每次取出当前需要学习的技能，然后将其还未学习的前置技能放入队列中，重复此操作即可。

另外，本题需要使用 vector 存储数据。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200010;

ll t[N];
vector<ll>a[N];
bool vis[N];

int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i];
        int m;cin>>m;
        for(int j=1;j<=m;j++){
            int x;cin>>x;
            a[i].push_back(x);
        }
    }

    ll res=0;
    queue<ll>q;
    q.push(n);
    vis[n]=true;
    while(!q.empty()){
        auto pos=q.front();q.pop();
        res+=t[pos];

        for(auto x:a[pos]){
            if(vis[x]) continue;

            q.push(x);
            vis[x]=true;
        }
    }
    cout<<res<<endl;
    return 0;
}