QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#749960#9431. The Quest for El DoradoYuuWA 125ms7156kbC++232.8kb2024-11-15 11:40:442024-11-15 11:40:45

Judging History

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

  • [2024-11-15 11:40:45]
  • 评测
  • 测评结果:WA
  • 用时:125ms
  • 内存:7156kb
  • [2024-11-15 11:40:44]
  • 提交

answer

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

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});
    }

    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::set<int>del;
        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);
                }else{
                    break;
                }
            }else{
                del.insert(v);
            }
        }

        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 : del){
            SG[c].erase(v);
        }

        for(auto v : newNode){
            vis[v] = 1;
            SG[c].erase(v);
        }

        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: 3592kb

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: -100
Wrong Answer
time: 125ms
memory: 7156kb

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:

1000000001000100000010000001000000000100000000
1000000010001001011011000000001000000100000000
1000000000000000000000000000000000000000000000
1011010000000010000100010011000100000000000010
1000000000000000000000101000010000001001000001
1000100010000000100000100000000000001010010
101010000000000000010...

result:

wrong answer 1st lines differ - expected: '1000110011110111110010100001010100100101000000', found: '1000000001000100000010000001000000000100000000'