QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300134#6306. Chase GameLittleXiWA 1ms3908kbC++172.0kb2024-01-07 18:58:342024-01-07 18:58:35

Judging History

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

  • [2024-01-07 18:58:35]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3908kb
  • [2024-01-07 18:58:34]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

ll n,m,k,d;
vector<vector<ll>> adj;
vector<ll> cau(ll st){
    vector<ll> re(n,0);
    vector<ll> vis(n,0);
    vis[st] = 1;
    queue<pair<ll,ll>> q;
    q.push({st,0});

    while(q.size()){
        auto&[x,dis] = q.front();q.pop();
        re[x] = dis;
        // cout<<x<<" "<<dis<<endl;
        for(auto to:adj[x]){
            if(vis[to]) continue;
            vis[to] = 1;
            q.push({to,dis+1});
        }
    } 
    return re;
}

vector<ll> f;

void init(){
    f = vector<ll> (n,0);
    f[0] = d;
    ll dis = 0;
    for(ll i =1;i<n;i++){
        dis++;
        if(dis==d) dis = 0;
        f[i] = f[i-1]+d-dis;
    }
    // for(ll x:f) cout<<x<<" ";
    // cout<<endl;
}


void solve(){
    cin>>n>>m>>k>>d;
    k--;
    adj = vector<vector<ll>> (n);
    for(ll i=0;i<m;i++){
        ll x,y;cin>>x>>y;x--;y--;
        adj[x].push_back(y);adj[y].push_back(x);
    }
    auto at_dis = cau(k);
    auto over_dis =cau(n-1);
    init();

    vector<ll> dp(n,1e18);
    
    vector<ll> vis(n,0);
    queue<ll> q;
    q.push(0);vis[0] = 1;dp[0]=0;
    ll ans = f[over_dis[0]-1];
    while(q.size()){
        ll x = q.front();q.pop();
        if(x!=0&&at_dis[x] >= d){
            ans = min(ans,dp[x]+f[over_dis[x]]);
            continue;
        }
        if(x==n-1){
            ans = min(ans,dp[n-1]);
            continue;
        }
        for(auto to:adj[x]){
            if(vis[to]) continue;
            if(at_dis[to]<d) dp[to] = min(dp[to],dp[x]+d-at_dis[to]);
            else dp[to] = min(dp[to],dp[x]);
            // cout<<x<<" "<<to<<" "<<dp[to]<<endl;
            vis[to] =1;q.push(to);
        }
    }
    cout<<ans<<endl;

}

/*
5 5 3 1
1 2
2 4
4 5
1 3
3 5
*/

signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    ll t = 1;
    // cin>>t;
    while(t--)
        solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 5 3 1
1 2
2 4
4 5
1 3
3 5

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

13 17 12 3
1 2
2 3
3 4
4 13
5 13
7 8
7 9
7 10
7 11
7 6
12 7
1 8
8 9
9 10
10 11
11 6
6 13

output:

7

result:

ok 1 number(s): "7"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

10 9 4 1
4 3
1 2
7 6
6 5
8 9
9 10
5 4
8 7
3 2

output:

9

result:

ok 1 number(s): "9"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3488kb

input:

10 20 9 1
9 5
2 9
4 5
10 5
7 3
1 8
7 1
7 5
3 4
3 1
7 8
3 8
9 3
10 6
9 1
1 6
8 5
6 2
1 10
2 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

10 20 3 1
1 4
6 7
5 4
5 3
2 1
8 1
7 8
2 6
2 4
4 8
9 5
1 10
7 4
5 8
4 10
2 5
6 10
4 6
3 7
1 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3436kb

input:

10 20 4 1
2 7
6 4
2 3
2 4
6 5
8 5
6 7
10 2
3 10
1 8
3 9
3 7
1 7
5 1
6 1
3 4
2 1
5 2
9 2
9 10

output:

2

result:

ok 1 number(s): "2"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

10 20 1 10
10 9
2 5
7 8
7 10
10 8
8 9
5 6
3 1
6 4
7 9
2 3
3 6
2 1
8 6
5 8
7 4
4 3
2 4
4 1
9 6

output:

24

result:

ok 1 number(s): "24"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

10 20 6 10
5 4
1 7
6 8
1 2
6 1
5 2
5 1
2 4
5 3
3 2
10 3
9 10
7 9
3 1
5 9
1 8
8 3
8 7
6 4
2 7

output:

15

result:

ok 1 number(s): "15"

Test #9:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

1000 999 387 1
505 506
314 313
410 411
680 681
884 885
491 492
60 59
343 342
396 397
880 881
954 953
833 834
53 54
284 283
794 793
241 240
347 348
89 88
787 786
551 550
673 672
56 57
683 682
168 169
814 813
726 725
877 876
981 982
799 800
228 227
568 569
387 386
211 212
30 29
298 299
514 515
561 562...

output:

999

result:

ok 1 number(s): "999"

Test #10:

score: 0
Accepted
time: 1ms
memory: 3896kb

input:

1000 2000 879 1
357 547
380 111
973 995
179 906
478 508
463 822
687 488
70 40
330 202
189 303
103 39
510 743
1000 236
311 695
29 338
156 77
299 249
289 275
419 57
352 704
739 825
676 194
783 828
769 169
270 325
354 29
145 197
309 461
456 461
997 816
478 387
117 626
931 803
445 91
730 160
1000 322
25...

output:

3

result:

ok 1 number(s): "3"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

1000 2000 603 228
10 11
885 884
217 218
626 629
559 562
305 302
328 326
809 807
176 179
553 554
435 432
641 639
761 763
486 484
376 374
261 260
515 512
224 222
413 414
33 34
468 470
976 979
461 459
491 490
272 275
528 526
393 396
673 676
45 42
677 676
247 249
938 937
200 203
649 647
303 304
457 455
...

output:

49209

result:

ok 1 number(s): "49209"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3908kb

input:

1000 2000 943 363
702 699
676 678
81 82
643 646
439 436
12 11
665 663
288 289
143 141
476 478
559 558
251 250
845 842
912 911
818 816
559 557
69 68
448 450
693 696
527 524
323 322
207 208
436 434
39 38
756 759
721 723
785 787
719 718
688 687
343 345
825 822
834 833
792 791
475 476
777 779
975 972
32...

output:

74162

result:

ok 1 number(s): "74162"

Test #13:

score: -100
Wrong Answer
time: 1ms
memory: 3748kb

input:

1000 2000 413 19
116 130
388 369
137 111
500 505
463 475
292 310
75 77
545 516
131 161
281 304
715 725
221 250
280 301
267 260
881 897
564 546
684 680
416 435
882 886
18 44
965 967
891 867
530 517
14 1
930 923
192 176
971 974
139 160
949 955
293 313
10 5
25 40
181 157
614 632
573 595
701 725
33 27
1...

output:

453

result:

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