QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#142574#6523. Escape PlanBUET_POTATOES#WA 1312ms68300kbC++201.4kb2023-08-19 12:35:532023-08-19 12:35:54

Judging History

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

  • [2023-08-19 12:35:54]
  • 评测
  • 测评结果:WA
  • 用时:1312ms
  • 内存:68300kb
  • [2023-08-19 12:35:53]
  • 提交

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


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1312ms
memory: 68300kb

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
11763
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'