QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#634961#8232. Yet Another Shortest Path QueryLateRegistration#WA 3719ms692804kbC++175.3kb2024-10-12 18:29:042024-10-12 18:29:04

Judging History

你现在查看的是最新测评结果

  • [2024-10-12 18:29:04]
  • 评测
  • 测评结果:WA
  • 用时:3719ms
  • 内存:692804kb
  • [2024-10-12 18:29:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<set<pair<int, int>>> g(n);
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        g[u].emplace(v, w);
        g[v].emplace(u, w);
    }
    set<pair<int, int>> s;
    for (int i = 0; i < n; i++) {
        s.emplace(g[i].size(), i);
    }
    while (!s.empty()) {
        auto [_, u] = *s.begin();
        s.erase(s.begin());
        for (auto [v, w] : g[u]) {
            s.erase({g[v].size(), v});
            g[v].erase({u, w});
            s.emplace(g[v].size(), v);
        }
    }
    int q;
    cin >> q;
    vector<int> res(q, INT_MAX);
    vector<tuple<int, int, int, int>> qs;
    vector<vector<tuple<int, int, int, int>>> q1(n), q2(n);
    vector<unordered_map<int, int>> mp(n);
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        s--, t--;
        qs.emplace_back(s, t, i, 0);
    }
    auto rec = [&](auto self, int k, vector<tuple<int, int, int, int>> qs) -> void {
        if (k == 1) {
            for (int i = 0; i < n; i++) {
                mp[i].clear();
            }
            for (int i = 0; i < n; i++) {
                for (auto [j, w] : g[i]) {
                    mp[i][j] = w;
                }
            }
            for (auto [s, t, id, inc] : qs) {
                if (mp[s].count(t)) {
                    res[id] = min(res[id], mp[s][t] + inc);
                } else if (mp[t].count(s)) {
                    res[id] = min(res[id], mp[t][s] + inc);
                }
            }
        } else if (k == 2) {
            vector<tuple<int, int, int, int>> nqs;
            for (auto [s, t, id, inc] : qs) {
                for (auto [x, w] : g[s]) {
                    nqs.emplace_back(x, t, id, inc + w);
                }
                for (auto [x, w] : g[t]) {
                    nqs.emplace_back(s, x, id, inc + w);
                }
            }
            self(self, k - 1, nqs);
            for (int i = 0; i < n; i++) {
                mp[i].clear();
            }
            vector<int> pre(qs.size(), -1), best(qs.size(), INT_MAX);
            for (int i = 0; i < qs.size(); i++) {
                auto [s, t, id, inc] = qs[i];
                if (!mp[s].count(t)) {
                    mp[s][t] = i;
                } else {
                    pre[i] = mp[s][t];
                }
            }
            for (int i = 0; i < n; i++) {
                for (auto [j, w1] : g[i]) {
                    for (auto [k, w2] : g[i]) {
                        if (mp[j].count(k)) {
                            int id = mp[j][k];
                            best[id] = min(best[id], w1 + w2);
                        }
                    }
                }
            }
            for (int i = 0; i < qs.size(); i++) {
                if (pre[i] != -1) {
                    best[i] = best[pre[i]];
                }
                if (best[i] != INT_MAX) {
                    auto [s, t, id, inc] = qs[i];
                    res[id] = min(res[id], best[i] + inc);
                }
            }
        } else if (k == 3) {
            vector<tuple<int, int, int, int>> nqs;
            for (auto [s, t, id, inc] : qs) {
                for (auto [x, w] : g[s]) {
                    nqs.emplace_back(x, t, id, inc + w);
                }
                for (auto [x, w] : g[t]) {
                    nqs.emplace_back(s, x, id, inc + w);
                }
            }
            self(self, k - 1, nqs);
            for (int i = 0; i < n; i++) {
                mp[i].clear();
            }
            vector<int> pre(qs.size(), -1), best(qs.size(), INT_MAX);
            for (int i = 0; i < qs.size(); i++) {
                auto [s, t, id, inc] = qs[i];
                if (!mp[s].count(t)) {
                    mp[s][t] = i;
                } else {
                    pre[i] = mp[s][t];
                }
            }
            for (int i = 0; i < n; i++) {
                for (auto [j, w1] : g[i]) {
                    if (i > j) continue;
                    for (auto [k, w2] : g[i]) {
                        for (auto [l, w3] : g[j]) {
                            if (mp[k].count(l)) {
                                int id = mp[k][l];
                                best[id] = min(best[id], w1 + w2 + w3);
                            }
                            if (mp[l].count(k)) {
                                int id = mp[l][k];
                                best[id] = min(best[id], w1 + w2 + w3);
                            }
                        }
                    }
                }
            }
            for (int i = 0; i < qs.size(); i++) {
                if (pre[i] != -1) {
                    best[i] = best[pre[i]];
                }
                if (best[i] != INT_MAX) {
                    auto [s, t, id, inc] = qs[i];
                    res[id] = min(res[id], best[i] + inc);
                }
            }
        }
    };
    rec(rec, 1, qs);
    rec(rec, 2, qs);
    rec(rec, 3, qs);
    for (int x : res) {
        cout << (x == INT_MAX ? -1 : x) << "\n";
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3576kb

input:

6 9
1 2 4
2 3 6
3 6 5
6 5 3
5 4 2
4 1 3
3 4 9
1 3 100
5 3 1
5
1 3
1 6
3 4
3 5
2 5

output:

6
8
3
1
7

result:

ok 5 number(s): "6 8 3 1 7"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

6 4
1 2 1
2 3 1
3 4 1
4 5 1
3
1 4
1 5
1 6

output:

3
-1
-1

result:

ok 3 number(s): "3 -1 -1"

Test #3:

score: -100
Wrong Answer
time: 3719ms
memory: 692804kb

input:

40005 79608
1 2 70031203
1 3 99924845
1 4 61645659
1 5 9324967
2 3 15761918
3 4 62534796
4 5 35260314
5 2 35948540
6 2 23727405
6 7 83302920
7 3 31010426
7 8 75060393
8 4 94275932
8 9 99663793
9 5 81701979
9 6 439297
10 6 46955645
10 11 89514237
11 7 21257310
11 12 53896253
12 8 67933315
12 13 26161...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

wrong answer 10648th numbers differ - expected: '149445856', found: '156403631'