QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#359364#6306. Chase GameSiilhouetteWA 1ms5752kbC++142.7kb2024-03-20 17:00:312024-03-20 17:00:31

Judging History

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

  • [2024-03-20 17:00:31]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5752kb
  • [2024-03-20 17:00:31]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long 

const int N=200010;
int n,m,K,D,inf,dis[2][N];

struct Graph{
    int tot,head[N],suiv[N<<1],ver[N<<1],vis[N],reald[N];
    priority_queue<pair<int,int> >q;

    inline void lnk(int x,int y)
    {
        ver[++tot]=y;
        suiv[tot]=head[x];
        head[x]=tot;
    }

    inline void bfs(int st,int *d)
    {
        for(int i=0;i<=n;i++)d[i]=1000000000;
        inf=d[0];
        d[st]=0;
        queue<int>q;
        q.push(st);
        while(q.size())
        {
            int x=q.front();q.pop();
            for(int i=head[x];i;i=suiv[i])
            {
                int y=ver[i];
                if(d[y]!=inf)continue;
                d[y]=d[x]+1;
                q.push(y);
            }
        }
    }

    inline void dijkstra(int st)
    {
        memset(reald,0x3f,sizeof(reald));
        reald[st]=0;
        q.push(make_pair(0,st));
        while(q.size())
        {
            int x=q.top().second;q.pop();
            if(vis[x])continue;
            vis[x]=1;
            //    cout<<"x "<<x<<endl;
            for(int i=head[x];i;i=suiv[i])
            {
                int y=ver[i],z=(D-dis[1][y])?D-dis[1][y]:D;
                if(dis[1][y]>D)continue;
                //   cout<<"y "<<y<<" "<<z<<endl;;
                if(reald[y]>reald[x]+z)
                {

                    reald[y]=reald[x]+z;
                    //      cout<<"reald "<<y<<" "<<reald[y]<<endl;
                    q.push(make_pair(-reald[y],y));
                }
            }
        }
    }

}e;

inline int cal(int t) // d-1 + d-2 + d-3 .... 1 + d + d-1 + d-2 .... t terms totally
{
    if(t<=D-1)
        return (D-1+D-1-t+1)*t/2;
    int tem=t-(t)/D*D;
    int lstdis=(t)/D*((1+D)*D)/2+(D-1+D-1-tem+1)*tem/2;
    return lstdis;
}

signed main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&K,&D);
    for(int i=1,x,y;i<=m;i++)
        scanf("%lld%lld",&x,&y),e.lnk(x,y),e.lnk(y,x);
    e.bfs(n,dis[0]);
    e.bfs(K,dis[1]);

    if(dis[1][1]>D)
    {
        int tem=dis[0][1]-(dis[0][1])/D*D;
        int lstdis=(dis[0][1])/D*((1+D)*D)/2+(D+D-tem+1)*tem/2;
        printf("%lld\n",lstdis);
        return 0;
    }

    e.dijkstra(1);
    int ans=1ll<<60;
    for(int i=1;i<=n;i++)
    {
        if(dis[1][i]==D)
        {
            //    cout<<"i"<<" "<<i<<endl;
            int lstdis=cal(dis[0][i]);
            //    cout<<lstdis<<endl;
            ans=min(ans,lstdis+e.reald[i]);
        }
    }
    if(ans==1ll<<60)ans=e.reald[n];
    printf("%lld\n",min(ans,e.reald[n]));
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 5320kb

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: 4084kb

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: 5356kb

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: 1ms
memory: 5360kb

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: 3828kb

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: 1ms
memory: 5432kb

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: 5412kb

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: 3900kb

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: 3844kb

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: 0ms
memory: 5752kb

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: 0ms
memory: 3888kb

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: 0
Accepted
time: 1ms
memory: 5740kb

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:

442

result:

ok 1 number(s): "442"

Test #14:

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

input:

1000 2000 970 42
924 920
773 772
926 923
887 916
143 121
525 547
17 3
55 63
884 871
840 853
821 846
161 155
87 83
515 521
146 168
940 911
881 876
107 84
898 920
156 144
489 518
706 709
599 569
396 420
806 808
68 48
619 645
407 411
955 951
144 160
173 167
243 240
217 195
191 205
729 750
809 796
914 9...

output:

1026

result:

ok 1 number(s): "1026"

Test #15:

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

input:

1000 2000 466 3
538 855
15 123
584 118
168 66
48 428
142 111
346 49
61 295
324 209
310 293
318 201
215 286
602 379
11 106
430 90
286 255
323 155
238 446
387 332
469 652
696 673
122 79
3 69
497 937
500 683
490 200
331 237
71 92
5 651
626 691
265 832
543 832
370 693
723 362
390 923
1 353
64 629
259 52...

output:

8

result:

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