QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#749930#9431. The Quest for El DoradoYuuTL 874ms153984kbC++233.0kb2024-11-15 11:32:022024-11-15 11:32:02

Judging History

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

  • [2024-11-15 11:32:02]
  • 评测
  • 测评结果:TL
  • 用时:874ms
  • 内存:153984kb
  • [2024-11-15 11:32:02]
  • 提交

answer

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

//  The 2024 ICPC Kunming Invitational Contest

/*
    Hint:
    1.维护一个集合S,S由已遍历过的点组成。
      维护S和非S点的边集{c, u, cost},假如存在多个cost,取最小的cost.
    2.限制性最短路.
*/

void sol(){
    int n, m, k;
    std::cin>>n>>m>>k;

    std::vector<std::map<int, std::vector<std::array<int, 2>>>>G(n + 1);
    for(int i = 1;i <= m;i++){
        int u, v, c, cost;
        std::cin>>u>>v>>c>>cost;
        G[u][c].push_back({v, cost});
        G[v][c].push_back({u, cost});
    }

    //  SG[c]:记录S的边集,c代表路的类型SG[c][v]:通过c路到达v的最低成本.
    std::vector<std::map<int, int>>SG(m + 1);
    std::vector<int>vis(n + 1);
    vis[1] = 1;

    {
        for(auto [c, V] : G[1]){
            for(auto [v, cost] : V){
                if(SG[c].count(v) == 0){
                    SG[c][v] = cost;
                }else{
                    SG[c][v] = std::min(SG[c][v], cost);
                }
            }
        }
    }

    const int inf = 1E18;
    std::vector<int>dis(n + 1, inf);

    auto calc = [&](int c, int U){
        std::set<int>newNode;
        std::priority_queue<std::array<int, 2>, std::vector<std::array<int, 2>>, std::greater<>>Q;
        for(auto [v, cost] : SG[c]){
            if(vis[v] == 0){
                if(cost <= U){
                    Q.push({dis[v] = cost, v});
                    newNode.insert(v);
                }
            }
        }

        //  不再使用S边集
        while(Q.size()){
            auto [cost, u] = Q.top();
            Q.pop();
            if(dis[u] < cost || G[u].count(c) == 0){
                continue ;
            }
            auto& E = G[u][c];
            for(auto [v, d] : E){
                if(vis[v] == 0){
                    if(cost + d < dis[v] && cost + d <= U){
                        Q.push({dis[v] = cost + d, v});
                        newNode.insert(v);
                    }
                }
            }
        }

        //  加入新的点
        for(auto v : newNode){
            vis[v] = 1;
            SG[c].erase(v);
        }

        //  拓展SG的边集
        for(auto u : newNode){
            for(auto& [cc, E] : G[u]){
                for(auto [v, cost] : E){
                    if(vis[v] == 0){
                        if(SG[cc].count(v) == 0){
                            SG[cc][v] = cost;
                        }else{
                            SG[cc][v] = std::min(SG[cc][v], cost);
                        }
                    }
                }
            }
        }
    };

    for(int i = 1;i <= k;i++){
        int c, U;
        std::cin>>c>>U;
        calc(c, U);
    }

    for(int i = 1;i <= n;i++){
        std::cout<<vis[i];
    }
    std::cout<<"\n";
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1; std::cin>>t;
    while(t--) sol();  
    return 0;
}

詳細信息

Test #1:

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

input:

2
5 6 4
1 2 1 30
2 3 1 50
2 5 5 50
3 4 6 10
2 4 5 30
2 5 1 40
1 70
6 100
5 40
1 30
3 1 1
2 3 1 10
1 100

output:

11011
100

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 250ms
memory: 7212kb

input:

1110
46 80 30
44 23 5 46
10 28 1 64
32 34 3 40
9 36 1 26
15 14 5 95
38 19 2 34
2 17 4 183
10 38 2 81
5 15 2 83
31 38 3 100
40 30 1 53
41 10 1 193
29 20 5 18
14 41 3 78
8 16 5 74
46 13 3 78
44 28 3 45
1 40 3 133
5 32 1 108
22 26 2 83
10 38 1 77
11 40 1 11
17 21 2 66
41 46 3 98
9 36 2 25
40 18 1 19
27...

output:

1000110011110111110010100001010100100101000000
1100010010111011011011000000011000001100001000
1000000000000000000000000000000000000000000000
1011010000000010000100010011000100000000000010
1000000000000000000000101000010000001001000001
1001100010110000100001100000000011001110110
101010000000000000010...

result:

ok 1110 lines

Test #3:

score: 0
Accepted
time: 181ms
memory: 8684kb

input:

1110
41 95 66
37 16 1 93
8 38 13 61
41 25 7 10
40 26 13 90
18 34 12 84
29 21 7 22
32 41 10 52
20 17 18 273
41 31 2 163
17 11 20 316
24 14 7 35
1 5 7 39
26 38 13 48
10 15 14 154
4 7 12 8
13 6 20 139
18 9 10 90
16 33 7 54
9 35 5 39
36 31 17 9
10 20 17 74
37 34 13 6
7 9 9 153
12 7 18 173
5 7 3 194
21 3...

output:

11111010101111111011111111101111111111011
11111111111111111111111111111111111111101
11111111111111111111111111111111111111111
11011110111111111111111111111011111111111
10100010011110000001010100010110010000001
111111111111111111111111111111111111111111
100000000000100000000000000100100000000000
1000...

result:

ok 1110 lines

Test #4:

score: 0
Accepted
time: 874ms
memory: 137564kb

input:

1
200000 500000 179
94800 107033 1 16
64316 117022 8 184
105481 172922 2 53
37627 148708 9 37
179021 41825 10 29
177650 69319 5 20
144968 160008 6 68
54796 172626 2 201
35718 99731 3 127
45553 132280 2 433
199580 18097 1 116
77143 7273 7 90
49300 94594 8 231
52637 197546 8 62
156375 4265 2 54
136509...

output:

111111111011001111111110110111111100000111111111111011101111011111110011111111011111111101100111111111110100111111101111111111111111111111111111111111111111111101111111111111111101111101010111111111111111110111111110111110111011010001110111111111111101111110011111111111111111110110111101011111111111...

result:

ok single line: '111111111011001111111110110111...1110101101101111110110011110111'

Test #5:

score: 0
Accepted
time: 724ms
memory: 153984kb

input:

1
200000 500000 28600
134923 17846 1145 19
38550 190638 1881 173
153445 161902 1019 61
134582 132451 1259 32
27836 81432 1053 99
45363 165206 1879 453
173218 82373 1834 392
36060 180829 1434 93
158792 24019 1305 80
114091 131741 400 36
86750 83631 674 284
102965 26889 903 96
72980 92116 852 293
7814...

output:

100101111101011111011110111110111110111001110111001100100011001111111011111101111011111010111010010010011101100111101010111010011101011111110111111101110110110111111111000110110101011110111011110111011011001111111101111110011111010111110100111111001111010110110111101111111011111101001011101110111010...

result:

ok single line: '100101111101011111011110111110...0111111111111110001011011001011'

Test #6:

score: 0
Accepted
time: 423ms
memory: 129084kb

input:

1
500000 500000 132
33565 62505 9 27
159690 223311 5 72
136509 402294 1 30
335433 250256 8 32
46344 199283 1 53
101509 318328 1 91
154342 472216 1 98
219655 19442 6 8
488718 58652 1 64
88757 14212 1 51
92129 332927 10 69
418031 387995 5 1
433240 214628 1 67
402161 87957 2 84
107282 385626 3 86
18834...

output:

100100000001001001011000000000010101010000100000000011010010000010000001000000100010000000101010100000011010001000011111000000101001000010010100101010110100010011000000000010000000111010101010011001011100000011000010100000001000010000001000010000001100010100000000001000010001000000001100110000010110...

result:

ok single line: '100100000001001001011000000000...0100010000000010000000000001101'

Test #7:

score: 0
Accepted
time: 515ms
memory: 131604kb

input:

1
500000 500000 34800
356922 276405 1274 6
70376 56771 944 85
311347 288381 114 23
323396 269923 1542 25
403829 492566 1731 41
415774 97020 149 48
317081 340484 627 3
277226 227941 1804 69
349022 434891 1274 53
436085 437523 1274 83
110761 403042 1180 86
333338 341167 1274 88
4802 451135 1149 18
116...

output:

111001100110001100011110001011001010001111100000011100001101000011100110010111011011101111101110010101011111110000111101100111101010111111100110001011111111101111100010101001110001110100100111010011110111001100011000111011111111111110010100111001111010011000111001111111111100111010001110011011111010...

result:

ok single line: '111001100110001100011110001011...1101000100101011111011001110110'

Test #8:

score: -100
Time Limit Exceeded

input:

1
200000 500000 500000
138435 172074 2 320
40030 9389 6 35
61974 124326 6 64
4679 144065 8 238
47254 185524 1 74
138009 134825 8 235
164764 59275 5 227
134478 183172 7 69
131920 51571 3 140
119971 193848 6 98
130747 49642 9 376
67838 127653 1 30
32972 140348 4 1
39560 183382 10 15
151497 1703 4 274
...

output:


result: