QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142580#6523. Escape PlanBUET_POTATOES#WA 1257ms67280kbC++201.4kb2023-08-19 12:41:402023-08-19 12:41:43

Judging History

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

  • [2023-08-19 12:41:43]
  • 评测
  • 测评结果:WA
  • 用时:1257ms
  • 内存:67280kb
  • [2023-08-19 12:41:40]
  • 提交

answer

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

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, int>pli;

const ll infl = 1e18;

void solv(){
    int n,m,k;
    cin>>n>>m>>k;
    vector< vector< pii > >g(n+1);
    vector<ll>D(n+1, infl);
    vector<int>baki(n+1);
    vector<int>startnods(k);
    for(int &x : startnods) cin>>x;
    for(int x : startnods) D[x] = 0;

    for(int i=1; i<=n; i++) cin>>baki[i];

    for(int i=0; i<m; i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    priority_queue< pli, vector<pli>, greater<pli> >pq; /// distance, node
    for(int x : startnods){
        for(auto [v,w] : g[x]) if(D[v]==infl) {
            pq.emplace( w, v );
        }
    }

    while(!pq.empty()){
        auto [dst, u] = pq.top();
        pq.pop();
        if(baki[u]){
            baki[u]--;
            continue;
        }
        D[u] = dst;
        for(auto [v,w] : g[u]) if(D[v]==infl){
            pq.emplace( D[u]+w, v );
        }
    }

    if(D[1]==infl){
        cout<<"-1\n";
    }
    else{
        cout<<D[1]<<"\n";
    }
}
/*
2
3 4 1
3
1 1 1
1 2 1
1 2 2
2 3 1
2 3 2
3 2 2
2 3
2 0 0
1 2 1
1 3 1
*/
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin>>tc;
    while(tc--){
        solv();
    }

    return 0;
}


詳細信息

Test #1:

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

input:

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

output:

4
-1

result:

ok 2 number(s): "4 -1"

Test #2:

score: -100
Wrong Answer
time: 1257ms
memory: 67280kb

input:

100
100 1808 2
94 47
3 3 0 2 4 3 3 4 0 0 2 2 2 3 2 4 0 2 3 4 4 2 0 3 4 3 1 0 2 1 2 2 0 3 4 4 4 1 2 2 3 1 0 0 3 1 4 2 1 3 3 4 3 0 4 1 0 3 2 1 4 4 1 3 2 3 3 3 3 1 0 3 0 4 3 1 0 4 0 4 4 1 2 0 0 4 1 3 3 3 0 2 2 1 1 2 3 4 1 2
72 29 1138
59 78 2398
95 5 1610
32 46 4176
36 99 8143
100 69 413
61 58 1595
9 9...

output:

13919
9039
12183
14028
13329
12072
10786
13408
10693
10661
12170
11759
10333
12396
11478
4580
11539
12073
12692
10455
18674
12942
11330
10757
15335
21490
11668
2322
10673
11049
11532
11308
8353
-1
12341
14285
11850
8993
11654
12808
8124
10795
24260
10965
14460
12766
-1
9076
10125
16724
-1
12235
1288...

result:

wrong answer 1st numbers differ - expected: '5109', found: '13919'