数据造的很好,但是很生气。
查看原帖
数据造的很好,但是很生气。
339311
mori_楼主2023/9/7 19:54

为什么堆优化的和slf的都卡了,普通的能过。这不合常理,

void spfa0 () {
    queue <int> q;
    rep (i, 1, n) h[i] = inf;
    q.emplace(0);
    inq.set(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (!inq.test(u)) continue;
        inq.reset(u);
        for (cat v : e[u]) {
            int tmp = v.w + h[u];
            if (h[v] > tmp) {
                h[v] = tmp, dep[v] = dep[u] + 1;
                if (dep[v] > n) { printf("-1"), exit(0); }
                if (!inq.test(v)) q.emplace(v);
                inq.set(v);
            }
        }
    }
}
void spfa0 () {
    deque <int> q;
    rep (i, 1, n) h[i] = inf;
    q.emplace_front(0);
    while (!q.empty()) {
        int u = q.front();
        q.pop_front();
        if (dep[u] > n) { printf("-1"), exit(0); }
        inq.reset(u);
        for (cat v : e[u]) {
            int tmp = v.w + h[u];
            if (h[v] > tmp) {
                h[v] = tmp, dep[v] = dep[u] + 1;
                if (dep[v] > n) { printf("-1"), exit(0); }
                if (q.empty() || tmp < q.front()) q.emplace_front(v);
                else if (!inq.test(v)) q.emplace_back(v);
                inq.set(v);
            }
        }
    }
}
2023/9/7 19:54
加载中...