开了 O2 MLE,没开 O2 TLE
#include <bits/stdc++.h>
using namespace std;
vector<int> G[10005];
int t[10005], vis[10005]; // t表示每项杂物需要的时间(len)
bitset<10005> in; // 入度是否不为0
struct nod {
int x, val;
nod(int x_, int val_) {
x = x_;
val = val_;
}
};
int read() { // 快读
int res = 0;
char ch;
while (true) {
ch = getchar_unlocked();
if (ch == -1 || ch == ' ' || ch == '\n') break;
if (ch >= '0' && ch <= '9') {
res *= 10;
res += ch-'0';
}
}
return res;
}
int main() {
ios::sync_with_stdio(false);
int n = read(), ans = 0;
for (int i = 1; i <= n; i++) {
i = read();
t[i] = read();
int v;
v = read();
while (v != 0) {
G[i].push_back(v);
in[v] = true;
v = read();
}
}
queue<nod> q;
for (int i = 1; i <= n; i++) {
if (!in[i]) {
q.push(nod(i, t[i]));
}
}
while (!q.empty()) {
auto [x, val] = q.front();
q.pop();
if (val <= vis[x]) continue; // 剪枝
ans = max(ans, val);
for (int i = 0; i < G[x].size(); i++) {
q.push(nod(G[x][i], val+t[G[x][i]])); // 加上这个点的点权(时间)
}
}
cout << ans << endl;
return 0;
}