QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#359351 | #6306. Chase Game | Siilhouette | WA | 2ms | 14312kb | C++14 | 2.8kb | 2024-03-20 16:49:33 | 2024-03-20 16:49:33 |
Judging History
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-(dis[0][1])/D*D;
int lstdis=(dis[0][1])/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;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 14312kb
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: 12056kb
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: 9972kb
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: 1ms
memory: 12100kb
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: 12028kb
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: 1ms
memory: 10212kb
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: 12064kb
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: 1ms
memory: 9988kb
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: 9996kb
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: 12036kb
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: 10032kb
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: 12308kb
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: 12004kb
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: 12100kb
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: 2ms
memory: 12332kb
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'