QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#228128#6523. Escape Plansjk1686959421WA 323ms31948kbC++202.3kb2023-10-28 12:21:492023-10-28 12:21:50

Judging History

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

  • [2023-10-28 12:21:50]
  • 评测
  • 测评结果:WA
  • 用时:323ms
  • 内存:31948kb
  • [2023-10-28 12:21:49]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 500010;
const int INF = 1e16+10;
typedef pair<int,int>PI;
int s[100010],ss[100010],d[100010];
struct cj{
    int a,b,c;
}e[1000010];
vector<int>t[100010];
bool cmp(cj x,cj y){
    if(x.a!=y.a){
        return x.a<y.a;
    }
    if(x.b!=y.b){
        return x.b<y.b;
    }
    return x.c<y.c;
}
void slove(){
    int n,m,k;
    cin>>n>>m>>k;
    map<PI,int>r;
    for(int i=1;i<=n;i++){
        s[i]=0;
        ss[i]=0;
        d[i]=1e16;
        t[i].clear();
    }
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        s[x]=1;
    }
    for(int i=1;i<=n;i++){
        cin>>ss[i];
    }
    for(int i=1;i<=m;i++){
        cin>>e[i].a>>e[i].b>>e[i].c;
    }
    sort(e+1,e+1+m,cmp);
    int cnt=0;
    /*for(int i=1;i<=m;i++){
        cout<<e[i].a<<' '<<e[i].b<<' '<<e[i].c<<endl;
    }*/
    for(int i=1;i<=m;i++){
        int a=e[i].a,b=e[i].b,c=e[i].c;
        if(e[i].a==e[i-1].a&&e[i].b==e[i-1].b){
            cnt++;
            if(ss[a]+1==cnt){
                r[{a,b}]=c;
                t[a].push_back(b);
            }
            if(ss[b]+1==cnt){
                r[{b,a}]=c;
                t[b].push_back(a);
            }
        }else{
            cnt=1;
            if(ss[a]+1==cnt){
                r[{a,b}]=c;
                t[a].push_back(b);
            }
            if(ss[b]+1==cnt){
                r[{b,a}]=c;
                t[b].push_back(a);
            }
        }
    }
    /*for(auto c:r){
        cout<<c.first.first<<' '<<c.first.second<<' '<<c.second<<endl;
    }*/
    queue<int>w;
    d[1]=0;
    w.push(1);
    int ma=INF;
    while(w.size()){
        int x=w.front();
        //cout<<x<<endl;
        if(s[x]){
            ma=min(ma,d[x]);
            //cout<<d[x]<<endl;
            //return;
        }
        w.pop();
        for(int i=0;i<t[x].size();i++){
            int y=t[x][i];
            //cout<<y<<endl;
            if(d[y]>d[x]+r[{x,y}]){
                d[y]=d[x]+r[{x,y}];
                w.push(y);
            }
        }
    }
    if(ma!=INF) cout<<ma<<endl;
    else cout<<-1<<endl;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        slove();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 323ms
memory: 31948kb

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:

-1
3729
-1
6471
3796
-1
-1
-1
-1
-1
-1
-1
1129
-1
2646
-1
-1
-1
-1
3532
-1
13774
-1
7646
-1
-1
-1
2322
13193
-1
-1
-1
1779
-1
12422
6265
5176
6560
-1
-1
537
3769
-1
12599
-1
-1
-1
510
-1
-1
-1
12229
-1
-1
-1
5770
-1
270
-1
8769
7464
-1
4387
-1
-1
-1
10496
-1
-1
7720
-1
20389
-1
-1
7982
6413
-1
-1
-1...

result:

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