QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#75492#5458. Shortest Path QueryJooDdaeTL 3ms6928kbC++171.5kb2023-02-05 14:12:282023-02-05 14:12:30

Judging History

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

  • [2024-06-21 12:37:11]
  • 管理员手动重测本题所有提交记录
  • 测评结果:TL
  • 用时:1ms
  • 内存:7072kb
  • [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:12:30]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:6928kb
  • [2023-02-05 14:12:28]
  • 提交

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()) {
                int X = 0, Y = 0;
                if(k == c[x].size() || (j < c[i].size() && (c[i][j][0] > c[x][k][0]+!y || (c[i][j][0] == c[x][k][0]+!y && c[i][j][1] > c[x][k][1]+y)))) {
                    X = c[i][j][0], Y = c[i][j][1], j++;
                } else {
                    X = c[x][k][0]+!y, Y = c[x][k][1]+y, k++;
                }
                while(!C.empty() && C.back()[1] > Y) C.pop_back();
                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: 3ms
memory: 6928kb

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
Time 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: