QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#75491#5458. Shortest Path QueryJooDdaeTL 0ms6944kbC++141.4kb2023-02-05 14:09:022023-02-05 14:09:06

Judging History

你现在查看的是测评时间为 2023-02-05 14:09:06 的历史记录

  • [2024-06-21 12:37:11]
  • 管理员手动重测本题所有提交记录
  • 测评结果:TL
  • 用时:2ms
  • 内存:7336kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-05 14:09:06]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:6944kb
  • [2023-02-05 14:09:02]
  • 提交

answer

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

int n, m, q, ans[50050];
vector<array<int, 2>> v[50050], c[50050];
vector<array<int, 3>> Q[50050];

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++) {
        int a, b, c; cin >> a >> b >> c;
        v[b].push_back({a, c});
    }
    cin >> q;
    for(int i=1;i<=q;i++) {
        int a, b, c; cin >> a >> b >> c;
        Q[c].push_back({a, b, i});
    }

    c[1].push_back({0, 0});
    for(int i=1;i<=n;i++) {
        c[i].push_back({n, n});
        for(auto [x, y] : v[i]) {
            vector<array<int, 2>> C;

            int j = 0, k = 0;
            while(j < c[i].size() || k < c[x].size()) {
                if(k == c[x].size() || (j < c[i].size() && c[i][j][0] >= c[x][k][0]+!y)) {
                    auto [X, Y] = c[i][j++];
                    C.push_back({X, Y});
                } else {
                    auto [X, Y] = c[x][k++];
                    (y ? Y : X) += 1;
                    C.push_back({X, Y});
                }
            }

            c[i] = C;
        }

        for(auto [a, b, id] : Q[i]) {
            ans[id] = INT_MAX;
            for(auto [x, y] : c[i]) ans[id] = min(ans[id], a*x + b*y);
        }

        if(i > 1000) c[i-1000].clear();
    }

    for(int i=1;i<=q;i++) cout << ans[i] << "\n";
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 6944kb

input:

4 4
1 2 0
1 3 1
2 4 0
3 4 1
3
3 5 2
3 2 4
2 3 4

output:

3
4
4

result:

ok 3 number(s): "3 4 4"

Test #2:

score: -100
Memory Limit Exceeded

input:

50000 100000
1 2 1
2 3 0
3 4 1
4 5 0
5 6 1
6 7 0
7 8 1
8 9 1
9 10 0
10 11 1
11 12 1
12 13 1
13 14 0
14 15 0
15 16 0
16 17 0
17 18 1
18 19 1
19 20 0
20 21 1
21 22 0
22 23 0
23 24 1
24 25 1
25 26 0
26 27 1
27 28 0
28 29 0
29 30 0
30 31 0
31 32 1
32 33 0
33 34 1
34 35 1
35 36 1
36 37 1
37 38 0
38 39 0
...

output:


result: