QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#274467 | #5073. Elden Ring | MaMengQi2 | WA | 308ms | 19728kb | C++14 | 2.0kb | 2023-12-03 15:47:56 | 2023-12-03 15:47:57 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int T,n,m,A,B,l[N];
#define ll long long
int dis[N],c[N],vis[N];
vector<int>e[N];
struct nod{
int id,val;
bool operator<(const nod&x)const{
return val>x.val;
}
};
priority_queue<nod>q;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&n,&m,&A,&B);
memset(dis,0x7f,sizeof(int)*(n+1));
for(int i=1;i<=n;i++)e[i].clear();
for(int i=1,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++)scanf("%d",&l[i]);
for(int i=2;i<=n;i++)
{
l[i]+=B;
if(A==B)c[i]=(l[i]<l[1])?1e9:-1;
else if(A<B)c[i]=l[i]<l[1]?(l[1]-l[i]-1)/(B-A):-1;
else
{
if(l[i]<l[1])c[i]=0;
else c[i]=(l[i]-l[1])/(A-B)+1;
}
// printf("%d ",c[i]);
}
// puts("");
if(A<=B)//最晚ci打
{
q.push((nod){1,0});
dis[1]=0;
while(!q.empty())
{
nod now=q.top();
q.pop();
// printf("now::%d %d\n",now.id,now.val);
if(dis[now.id]!=now.val)continue;
for(int to:e[now.id])
{
if(dis[now.id]<=c[to]&&dis[to]>dis[now.id]+1)
{
dis[to]=dis[now.id]+1;
q.push((nod){to,dis[to]});
}
}
}
printf("%d\n",dis[n]>=5e8?-1:dis[n]);
}
else
{
memset(vis,0,sizeof(int)*(n+1));
q.push((nod){1,0});
vis[1]=2;
int Nl=l[1];
while(!q.empty())
{
nod now=q.top();
q.pop();
if(now.val>=Nl)continue;
vis[now.id]=2;
if(now.id!=1)Nl+=A-B;
for(int to:e[now.id])
if(!vis[to])q.push((nod){to,l[to]}),vis[to]=1;
}
q.push((nod){1,0});
dis[1]=0;
if(vis[n]==2)
while(!q.empty())
{
nod now=q.top();
q.pop();
if(dis[now.id]!=now.val)continue;
for(int to:e[now.id])
if(vis[to]==2&&dis[to]>max(dis[now.id],c[to])+1)
{
dis[to]=max(dis[now.id],c[to])+1;
q.push((nod){to,dis[to]});
}
}
printf("%d\n",dis[n]>=5e8?-1:(dis[n]));
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 11324kb
input:
2 5 4 5 8 1 2 1 3 1 4 4 5 15 1 1 1 1 5 4 10 5 1 2 1 3 1 4 4 5 10 4 4 4 19
output:
2 4
result:
ok 2 number(s): "2 4"
Test #2:
score: 0
Accepted
time: 154ms
memory: 11016kb
input:
100000 6 10 107812 105568 6 5 3 6 4 6 4 2 5 1 5 6 4 5 1 3 1 2 2 5 124065 140875 29890 80077 116532 35394 9 10 82107 88302 1 2 2 3 5 3 5 1 1 4 9 6 3 5 8 2 5 6 7 5 22670 3735 33660 92823 139960 89319 83335 158330 117349 6 10 181257 173221 5 3 3 4 3 1 5 1 2 1 3 6 3 1 6 2 3 6 4 3 76902 46253 123092 2661...
output:
-1 -1 -1 1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 2 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 ...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 147ms
memory: 11628kb
input:
100000 10 10 7791 61545 9 3 3 10 7 4 2 1 3 4 2 6 8 2 2 3 5 2 3 2 142757 98694 34871 181188 28671 62924 172723 13856 11576 26661 10 10 194165 132103 2 5 8 7 3 1 7 3 1 2 6 1 4 9 1 3 4 3 10 4 176824 47360 148701 4531 66460 199228 135267 149448 65763 125940 9 10 152778 128023 3 1 3 2 1 2 1 6 5 7 5 2 4 7...
output:
-1 -1 7 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 4 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 -1 1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 1 3 -1 -1 1 1 -1 -1 -1 5 1 -1 -1 -1 -1 -1 -1 -1 -...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 127ms
memory: 10636kb
input:
10000 95 100 88670 88078 80 65 52 30 18 23 62 56 2 1 11 20 69 32 65 35 44 92 38 14 81 89 19 3 15 46 2 24 85 6 8 21 59 51 27 17 17 33 25 23 44 12 63 57 29 9 36 34 9 81 3 8 41 11 58 93 42 15 12 15 17 14 16 73 21 60 94 21 87 5 6 67 91 43 18 8 23 54 83 69 82 79 23 95 26 47 46 8 22 21 9 5 30 5 50 14 56 5...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
ok 10000 numbers
Test #5:
score: 0
Accepted
time: 133ms
memory: 10480kb
input:
10000 55 100 45240 42375 2 30 41 35 44 42 20 27 25 7 43 22 14 12 25 48 2 1 48 39 22 55 28 4 13 21 2 5 27 2 18 42 18 52 34 13 50 6 6 47 6 5 37 5 35 36 31 23 12 24 1 44 9 3 9 1 7 35 26 45 44 48 27 49 40 43 34 9 43 47 26 42 49 28 53 31 11 32 8 6 22 27 23 32 6 54 1 16 22 11 34 20 21 44 31 2 9 22 23 5 1 ...
output:
-1 -1 -1 4 5 -1 6 -1 13 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 7 -1 -1 4 -1 12 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 1 18 -1 14 5 5 -1 -1 3 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 14 15 -1 -1 -1 -1 -1 -1 -...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 140ms
memory: 10724kb
input:
10000 78 100 3273 35629 51 26 12 13 60 57 67 56 34 9 7 44 3 6 63 5 6 75 49 36 63 36 9 10 10 20 8 16 58 29 10 41 4 5 4 78 35 70 68 72 11 3 20 66 18 2 14 25 21 22 52 18 21 23 24 43 51 32 19 49 38 37 28 54 9 73 24 30 21 32 10 40 4 29 4 67 55 32 27 33 38 39 13 37 4 68 20 26 73 37 60 67 4 9 15 41 12 1 2 ...
output:
-1 2 -1 -1 -1 -1 -1 3 -1 -1 6 2 -1 -1 -1 -1 -1 4 -1 -1 17 -1 5 5 8 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 2 9 -1 -1 6 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 3 6 5 -1 -1 3 -1 -1 -1 -1 3 3 -1 4 -1 -1 5 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 7 7 -1 -1 3 -1 -1 -1 1...
result:
ok 10000 numbers
Test #7:
score: 0
Accepted
time: 132ms
memory: 11076kb
input:
1000 765 1000 38769 38790 686 640 40 43 94 451 1 2 511 661 671 166 683 265 398 722 759 707 245 19 1 12 613 166 227 305 220 93 18 1 28 41 183 392 718 314 184 82 190 436 361 405 35 71 507 136 407 226 101 2 513 252 287 757 684 645 347 389 91 81 299 690 158 744 380 457 193 136 170 393 467 1 70 103 138 2...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 15 -1 -1 -1 -1 -1 11 -1 -1 16 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 8 -1 -1 3 3 -1 -1 -1 -1 ...
result:
ok 1000 numbers
Test #8:
score: 0
Accepted
time: 139ms
memory: 10804kb
input:
1000 686 1000 122539 123067 518 504 263 59 629 1 539 315 122 296 182 406 347 370 4 106 143 70 70 50 298 24 373 201 84 16 44 509 241 127 562 495 54 8 198 651 207 341 625 378 185 148 468 35 279 181 95 47 581 197 338 488 44 204 572 43 362 577 340 489 561 671 20 414 526 500 496 380 300 675 564 105 647 3...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 112 -1 -1 -1 -1 -1 -1 -1 -1 -1 159 -1 -1 110 -1 -1 -1 -1 45 -1 -1 -1 -1 -1 -1 -1 16 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 80 48 7 86 -1 -1 -1 -1 -1 -1...
result:
ok 1000 numbers
Test #9:
score: 0
Accepted
time: 149ms
memory: 9940kb
input:
1000 769 1000 77850 85984 175 700 495 653 251 294 542 472 91 40 572 277 10 395 99 532 293 577 326 37 256 194 529 604 476 61 324 709 304 561 740 728 406 586 354 352 380 146 622 98 120 217 734 559 79 93 125 573 251 178 312 164 451 250 677 606 707 767 193 718 40 678 433 588 147 46 524 685 126 262 22 59...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 20 11 -1 -1 -1 15 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 21 -1 -1 -1 -1 -1 -1 -1 -1 14 -1 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 21 -1 40 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 29 -1 -1 13 13 -1 -1 -1 11 25 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 71 -1 -1 -1 2 -1 -1 -1 -...
result:
ok 1000 numbers
Test #10:
score: 0
Accepted
time: 149ms
memory: 10788kb
input:
1000 537 1000 87972 185707 259 391 306 317 260 293 479 379 284 458 43 68 194 262 239 527 135 294 175 320 211 45 145 218 28 1 166 113 90 484 118 407 50 459 61 137 259 101 358 278 91 345 487 141 407 226 40 207 119 204 19 183 2 1 21 4 161 220 531 336 109 108 324 78 521 471 230 368 458 535 209 138 132 3...
output:
-1 7 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 6 -1 -1 8 -1 4 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 9 -1 -1 -1 -1 -1 -1 -1 11 5 -1 -1 -1 -1 7 -1 7 -1 5 -1 -1 -1 -1 6 4 -1 6 -1 -1 -1 11 -1 -1 -1 -1 -1 -1 6 -1 7 -1 -1 7 3 3 11 6 5 7 -1 -1 -1 -1 4 -1 -1 -1 -1 8 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1...
result:
ok 1000 numbers
Test #11:
score: 0
Accepted
time: 158ms
memory: 12272kb
input:
100 7926 10000 63093 63190 1980 3456 155 3681 587 7801 7767 4127 4187 5514 490 6503 2265 5486 5212 2711 5786 3166 7872 5929 1000 1312 4271 3471 7342 1202 4063 6730 4556 2811 7278 3281 6235 5894 584 3136 1328 20 6103 2612 577 950 6559 5859 4539 4158 3149 3042 454 4580 1804 5691 6140 6099 3363 1432 18...
output:
-1 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 2282 4168 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 419 -1 -1 -1 485 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 1273 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 100 numbers
Test #12:
score: 0
Accepted
time: 150ms
memory: 10888kb
input:
100 6857 10000 68420 69012 2703 28 2696 4445 5949 1124 6482 4800 493 315 921 5817 5452 5485 5469 2870 3584 4964 5243 5027 5592 6549 3987 2838 2408 2208 4295 2505 4292 4590 3043 6204 2686 480 5405 1630 1012 2166 6432 5467 1850 2079 598 958 2331 2992 130 1734 2253 243 439 959 1887 593 6378 5186 1244 2...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 323 -1 -1 -1 -1 -1 -1 -1 -1 56 -1 -1 -1 -1 -1 -1 26 -1 -1 -1 -1 -1 -1 -1 -1 30 -1 -1 -1 -1 -1 -1 -1 -1 116 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 124 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 172 14 -1 -1 -1 -1 -1 -1 389 -1 -1 -1 -1 -1 -1 -1 -1 -...
result:
ok 100 numbers
Test #13:
score: 0
Accepted
time: 173ms
memory: 11232kb
input:
100 8353 10000 153179 157653 188 2789 3672 1885 3775 7223 408 5334 702 6886 6767 7941 7634 5751 6437 6953 4662 3122 5355 6159 1799 945 6833 596 1953 5894 5429 2697 3587 2589 1205 5388 2475 1482 306 1453 2625 2019 5179 5325 416 2473 6823 1919 185 1711 551 2513 1075 1352 2015 3007 1661 5547 1142 1431 ...
output:
-1 17 -1 -1 -1 17 -1 -1 -1 -1 -1 27 8 15 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 12 -1 -1 -1 -1 -1 16 -1 -1 -1 12 -1 -1 -1 -1 -1 13 -1 -1 -1 -1 -1 -1 -1 -1 17 -1 6 -1 -1 -1 -1 13 -1 -1 -1 -1 -1 -1 -1 -1 -1 10 20 21 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 77 -1 15 -1 -1 -1 -1 -1 24 -1 -1 -1 -1 34
result:
ok 100 numbers
Test #14:
score: 0
Accepted
time: 181ms
memory: 11180kb
input:
100 6069 10000 112617 78969 2106 5035 3943 1517 1288 10 5693 5136 905 525 5652 1065 2661 2717 846 1836 580 4265 3973 1342 5893 3265 1471 742 2150 2494 432 5731 96 605 534 3512 5589 2018 1591 701 1255 407 1645 5378 500 2486 427 5624 5739 2164 5760 1187 1723 4511 1709 5461 1441 1065 636 5295 891 4529 ...
output:
8 -1 12 -1 -1 -1 6 4 12 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10 11 -1 10 -1 -1 8 -1 -1 -1 -1 8 15 -1 -1 -1 10 -1 -1 -1 10 -1 7 -1 -1 -1 7 -1 -1 -1 19 -1 -1 -1 -1 -1 6 -1 -1 -1 9 18 -1 8 -1 9 -1 -1 -1 7 -1 -1 -1 8 -1 -1 -1 -1 9 -1 -1 -1 7 -1 -1 -1 -1 23 7 9
result:
ok 100 numbers
Test #15:
score: 0
Accepted
time: 283ms
memory: 18956kb
input:
5 158995 200000 153696 153721 117979 88926 141536 92027 97977 60542 106020 56072 5835 31943 72861 48346 43307 13999 25048 11650 99687 2750 18617 35290 109969 13716 110456 42158 29866 110431 40896 79959 81031 77614 155386 102161 41309 32980 119950 145249 12492 14566 50752 99261 61527 43732 33130 8869...
output:
-1 -1 1263 -1 -1
result:
ok 5 number(s): "-1 -1 1263 -1 -1"
Test #16:
score: 0
Accepted
time: 273ms
memory: 18912kb
input:
5 162800 200000 20986 20210 4407 40416 150939 35523 130520 77709 126667 28153 71668 80108 16326 18938 10050 13123 58961 31630 24935 8802 4796 48343 4103 5016 73874 123015 109156 83937 94447 141998 12908 2946 93319 157762 74555 89835 15082 7573 113766 15131 108660 117951 57866 47839 46346 37497 54199...
output:
8 -1 -1 -1 -1
result:
ok 5 number(s): "8 -1 -1 -1 -1"
Test #17:
score: 0
Accepted
time: 308ms
memory: 19728kb
input:
5 168622 200000 151296 149635 84739 139477 42303 34850 93689 83697 1033 2094 38924 39560 155 108683 153709 52427 46680 77616 27842 78754 22461 12848 1857 89005 115080 43124 104649 129157 9787 14153 49442 108488 148731 103097 43258 95978 86323 102855 9437 45553 85495 121862 103625 57113 110516 80058 ...
output:
-1 16 -1 15 -1
result:
ok 5 number(s): "-1 16 -1 15 -1"
Test #18:
score: -100
Wrong Answer
time: 239ms
memory: 18716kb
input:
5 149776 200000 126566 56475 17108 18243 146419 13993 69520 111344 4321 57900 114456 15257 28726 7586 4175 42517 138503 40503 149333 66558 89090 29116 75015 135950 35754 91228 70791 10899 41687 27752 91975 91127 30194 23735 146095 116856 83653 110470 92582 53620 80846 137377 67115 117987 4331 90449 ...
output:
-1 -1 -1 -1 -1
result:
wrong answer 4th numbers differ - expected: '16', found: '-1'