頂点が番号付けられている\(N\) 頂点からなるグラフであって、頂点 \(i\) \((1\leq i\leq N)\) から頂点 \(A_{i,j}\) \((1\leq j\leq K_i)\) に有向辺をはったグラフを考えます。このとき, 辺で直接結ばれている \(2\) 頂点のうち, つねに大きい番号の頂点から小さい番号の頂点の方へ辺が結ばれていることに注意します。

このグラフにおいて、頂点 \(N\) から頂点 \(V\) \((1\leq V\leq N-1)\) へいくつかの辺を辿って到達可能であるとき、技 \(N\) を習得するためには必ず技 \(V\) を習得している必要があります。なぜなら、グラフ上で \(N\) から \(V\)への経路を \(1\) つとり, 経路上の頂点 (端点を含む) を、順に\(u_1(=N), u_2, \ldots, u_m(=V)\) とすると、\(1\leq i\leq m-1\) について、技 \(u_i\) を習得する修練を開始する時点で技 \(u_{i+1}\) をすでに習得していなければならないからです。 よって、頂点 \(U\) から到達可能な頂点( \(U\) 自身を含む)の集合を\(S\), \(S\)の元を番号が小さい方から順に \(V_1,V_2, \ldots, V_{\lvert S\rvert}\) とすると、技 \(N\) を習得するのに、少なくとも時間\(\displaystyle\sum_{i=1}^{\lvert S\rvert}T_{V_i}\)はかかることがわかります。

逆に、このとき\(i=1,2,\ldots, \lvert S\rvert\)の順で技 \(V_i\) に対する修練を行うことが出来ることを示します。任意の\(1\leq i\leq \lvert S\rvert\)および\(1\leq j\leq K_{V_i}\) について, 上で考えたグラフにおいて、頂点 \(N\) から頂点\(A_{V_i,j}\) へは 頂点 \(V_i\) を経由して到達可能です。よって、\(A_{V_i,j}\in S\)であり、\(A_{V_i,j}<V_i\) よりある\(i'<i\) を用いて \(V_{i'}\) と書けます。よって、技 \(V_i\) に対する修練を始める時点ですでに技 \(A_{V_i,j}\) は習得済みであり、上の順で修練を行う事が出来ることが分かりました。

以上より、答えは上のように \(S\) および \(V_1,V_2, \ldots, V_{\lvert S\rvert}\) を定めたときの　\(\displaystyle\sum_{i=1}^{\lvert S\rvert}T_{V_i}\) となります。

頂点 \(N\) から到達可能な頂点集合については、上のグラフにおける辺の本数が \(M=\displaystyle\sum_{i=1}^{N} K_i\)であることに注意すると、BFS(幅優先探索)やDFS(深さ優先探索)などによって、\(O\left( N+\displaystyle\sum_{i=1}^{N} K_i \right) \) で求めることができます。よって、この問題を解くことが出来ました。

c++による実装例:

#include <bits/stdc++.h>

using namespace std;
 
#define N 200100
#define MOD 998244353
#define ll long long
#define rep(i, n) for(int i = 0; i < n; ++i)

ll t[N];
int k[N];
vector<int>e[N];

bool used[N];

int main(void) {
	int n, x;
	ll ans = 0;
	rep(i, N)used[i] = false;

	cin >> n;
	rep(i, n) {
		cin >> t[i];
		cin >> k[i];
		rep(j, k[i]) {
			cin >> x;
			e[i].push_back(x - 1);
		}
	}

	used[n - 1] = true;
	for (int i = n - 1; i >= 0; i--) {
		if (used[i]) {
			ans += t[i];
			rep(j, k[i]) {
				used[e[i][j]] = true;
			}
		}
	}

	cout << ans << endl;

	return 0;
}