QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#228113#6523. Escape Plansjk1686959421WA 313ms32152kbC++202.5kb2023-10-28 12:12:002023-10-28 12:12:01

Judging History

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

  • [2023-10-28 12:12:01]
  • 评测
  • 测评结果:WA
  • 用时:313ms
  • 内存:32152kb
  • [2023-10-28 12:12:00]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 500010;
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(i==0){
            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);
            }
        }
        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);
    while(w.size()){
        int x=w.front();
        //cout<<x<<endl;
        if(s[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);
            }
        }
    }
    cout<<"-1"<<endl;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _=1;
    cin>>_;
    while(_--){
        slove();
    }
}

详细

Test #1:

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

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: 313ms
memory: 32152kb

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
9039
-1
6471
5555
-1
-1
-1
-1
-1
-1
-1
3249
-1
5513
-1
-1
-1
-1
3952
-1
13774
-1
14329
-1
-1
-1
2322
13546
-1
-1
-1
4157
-1
18783
6265
6264
8993
-1
-1
8124
3769
-1
12599
-1
-1
-1
510
-1
-1
-1
14645
-1
-1
-1
5770
-1
270
-1
11967
10221
-1
6710
-1
-1
-1
10521
-1
-1
11903
-1
21551
-1
-1
7982
12604
-1...

result:

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