拓扑排序50pts求优化
查看原帖
拓扑排序50pts求优化
1013950
__youzimo2014__楼主2024/8/24 17:11

开了 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;
}

2024/8/24 17:11
加载中...