QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#628323 | #9293. Fine Trip | xlwang | AC ✓ | 15ms | 8916kb | C++14 | 2.2kb | 2024-10-10 19:37:29 | 2024-10-10 19:37:29 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define fr(i,j,k) for(register int i=j;i<=k;++i)
#define rf(i,j,k) for(register int i=j;i>=k;--i)
#define foredge(i,j) for(register int i=head[j];i;i=e[i].nxt)
#define pb push_back
#define ldb long double
#define Times printf("Time:%.3lf\n",clock()/CLOCKS_PER_SEC)
#define pii pair<int,int>
#define mk make_pair
using namespace std;
inline int read(){
int x=0;
bool f=0;
char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return f?-x:x;
}
inline void write(int x){
if(x<0){putchar('-');x=-x;}
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void writeln(int x){write(x); puts("");}
inline void writepl(int x){write(x); putchar(' ');}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int randfind(int l,int r){return rnd()%(r-l+1)+l;}
//inline void init(){
// int t=read();
// while(t--) work();
//}
const int Maxn=2e3+10,Maxm=1e5+10;
const ldb inf=1e30;
ldb f[Maxn];
struct node{
int pos;
ldb dis;
bool operator < (const node &p) const {return dis>p.dis;}
};
int n,m,T;
vector<pair<int,double> > vc[Maxn];
inline void init(){
n=read();m=read();T=read();
fr(i,1,m){
int x,y,l,c;
x=read();y=read();l=read();c=read();
vc[x].pb(mk(y,1ll*l*c));
vc[y].pb(mk(x,1ll*l*c));
}
}
int vis[Maxn];
inline ldb getans(ldb x,ldb y){return x+y+2*sqrt(x*y);}
inline void work(){
fr(i,1,n) f[i]=inf;f[1]=0;
priority_queue<node> q;q.push((node){1,0});
while(!q.empty()){
node tmp=q.top();q.pop();
int x=tmp.pos;ldb d=tmp.dis;
if(vis[x]) continue;vis[x]=1;
for(auto p:vc[x]){
int y=p.first;
// cout<<"**"<<p.first<<' '<<p.second<<endl;
if(f[y]>getans(d,p.second)){
f[y]=getans(d,p.second);
if(!vis[y]) q.push((node){y,f[y]});
}
}
}
printf("%.10Lf\n",f[n]/T);
}
signed main(){
// freopen("input.in","r",stdin);
// freopen("output.out","w",stdout);
init();work();
// printf("\nTIME:%.3lf",(double)clock()/CLOCKS_PER_SEC);
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4008kb
input:
3 3 100 1 3 100 100 1 2 100 24 2 3 100 24
output:
96.0000000000
result:
ok found '96.0000000', expected '96.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
3 2 10 1 2 9 1 2 3 1 1000
output:
119.8736659610
result:
ok found '119.8736660', expected '119.8736660', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
4 5 9 1 2 6 7 1 3 6 2 2 3 8 7 2 4 3 4 3 4 1 7
output:
4.1478114200
result:
ok found '4.1478114', expected '4.1478114', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3996kb
input:
100 150 986428838 91 64 507238859 759737815 75 4 403581576 658994630 57 21 725237383 935111999 40 87 981276800 673193011 11 43 80691506 709831037 41 89 50163377 373453345 58 36 274674403 292610326 68 54 831628941 850969830 72 28 678792191 467183610 32 92 372884862 179215422 18 6 667244829 651862998 ...
output:
1150229105.4195334262
result:
ok found '1150229105.4195335', expected '1150229105.4195333', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4108kb
input:
1000 2000 751953739 231 51 525528324 92998197 27 801 937206436 934125752 643 246 61249450 770328651 751 425 477644405 668859178 10 909 957408199 744724197 633 815 285485672 768445000 494 832 120397048 965104568 279 691 223555510 673873811 222 940 347142265 94216867 398 15 584774429 785975052 207 914...
output:
2496450976.9642393324
result:
ok found '2496450976.9642391', expected '2496450976.9642396', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4244kb
input:
1000 2000 676041401 521 438 669190473 775071143 163 702 423377467 702423309 210 913 925484961 92183256 78 277 469027016 633215062 688 933 740317061 452458210 440 259 913889125 581064794 770 659 440321238 52463558 26 954 8034890 199878681 807 707 299275249 470938197 184 691 208821530 862059495 310 70...
output:
4087930881.3530260904
result:
ok found '4087930881.3530259', expected '4087930881.3530254', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4232kb
input:
1500 2000 48051440 1166 923 86 765114530 799 885 26 816688991 392 193 38 986515706 935 1270 72 11859387 212 1454 77 934621041 1264 378 41 446614584 86 889 64 712840828 760 228 28 163912062 387 986 46 747169233 237 1423 9 880695780 655 1446 10 624077866 906 1178 5 899310944 1083 458 28 234637440 212 ...
output:
38723.1255704047
result:
ok found '38723.1255704', expected '38723.1255704', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4040kb
input:
1500 2000 541208001 1310 1388 896797634 462933014 1362 1288 964762034 547937510 731 423 757703169 250510444 1225 1228 763458414 870985242 977 1248 542259061 232556189 962 67 96821377 321933340 222 538 997161193 198113674 732 1083 356475754 169084966 572 93 689277455 528186960 420 1359 553405642 9444...
output:
12841383894.8144963849
result:
ok found '12841383894.8144970', expected '12841383894.8144989', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
4 4 964438192 2 4 216592581 216592586 1 2 216592587 216592580 3 4 216592587 216592580 1 3 216592582 216592585
output:
194568600.1087126753
result:
ok found '194568600.1087127', expected '194568600.1087127', error '0.0000000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 4232kb
input:
2000 5997 87143309 1 2 194316880 17603954 1 2 578807298 211924703 1 2 35049332 747662405 2 3 727054473 20228268 2 3 158011027 703403545 2 3 315088812 192695808 3 4 538566789 310645560 3 4 288674415 674518964 3 4 641633573 895765856 4 5 18150295 795900151 4 5 8912085 300347747 4 5 153073571 839721646...
output:
2809268677693526.5917968750
result:
ok found '2809268677693526.5000000', expected '2809268677693535.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 1ms
memory: 4100kb
input:
1999 2664 674663437 1779 1780 252 252 106 108 72 64 119 121 206 206 1583 1585 249 258 66 67 237 243 1922 1924 308 318 1004 1006 146 143 1021 1023 263 255 49 51 293 296 1414 1416 175 180 962 964 148 147 1489 1490 132 125 1914 1915 101 100 740 742 158 168 444 445 147 152 1712 1714 296 307 1291 1292 23...
output:
115.0037507326
result:
ok found '115.0037507', expected '115.0037507', error '0.0000000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 4168kb
input:
1999 2664 480837973 83 85 261334650 261334658 1555 1557 279350528 279350526 1550 1552 267088737 267088735 831 832 222476224 222476216 986 988 167425748 167425741 1617 1618 311263734 311263745 629 631 292124045 292124054 290 292 282890879 282890888 671 673 267550747 267550746 1021 1023 167856083 1678...
output:
161986637988800.8251190186
result:
ok found '161986637988800.8125000', expected '161986637988800.9062500', error '0.0000000'
Test #13:
score: 0
Accepted
time: 1ms
memory: 4060kb
input:
2000 1999 1 1 2 1000000000 1000000000 2 3 1000000000 1000000000 3 4 1000000000 1000000000 4 5 1000000000 1000000000 5 6 1000000000 1000000000 6 7 1000000000 1000000000 7 8 1000000000 1000000000 8 9 1000000000 1000000000 9 10 1000000000 1000000000 10 11 1000000000 1000000000 11 12 1000000000 10000000...
output:
3996001000000000000000000.0000000000
result:
ok found '3996001000000000253493248.0000000', expected '3996001000000000253493248.0000000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 4196kb
input:
2000 1999 1000000000 1 2 1000000000 1000000000 2 3 1000000000 1000000000 3 4 1000000000 1000000000 4 5 1000000000 1000000000 5 6 1000000000 1000000000 6 7 1000000000 1000000000 7 8 1000000000 1000000000 8 9 1000000000 1000000000 9 10 1000000000 1000000000 10 11 1000000000 1000000000 11 12 1000000000...
output:
3996001000000000.0000000000
result:
ok found '3996001000000000.0000000', expected '3996001000000000.0000000', error '0.0000000'
Test #15:
score: 0
Accepted
time: 0ms
memory: 4016kb
input:
100 500 1 98 50 1 1 83 2 1 1 82 57 1 1 9 100 1 1 82 50 1 1 99 53 1 1 12 62 1 1 77 71 1 1 35 54 1 1 44 40 1 1 45 8 1 1 7 29 1 1 64 25 1 1 14 81 1 1 35 54 1 1 55 15 1 1 24 56 1 1 58 37 1 1 49 87 1 1 67 44 1 1 4 42 1 1 34 16 1 1 75 77 1 1 55 15 1 1 53 99 1 1 80 48 1 1 65 37 1 1 91 9 1 1 46 19 1 1 53 35...
output:
2809.0000000000
result:
ok found '2809.0000000', expected '2809.0000000', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
100 500 1 90 27 1 1 21 100 1 1 1 6 1 1 99 11 1 1 97 16 1 1 25 78 1 1 61 69 1 1 11 50 1 1 89 66 1 1 88 22 1 1 62 51 1 1 82 60 1 1 63 57 1 1 26 41 1 1 93 42 1 1 13 23 1 1 76 61 1 1 90 48 1 1 99 33 1 1 70 14 1 1 35 68 1 1 73 94 1 1 32 11 1 1 49 12 1 1 70 93 1 1 79 90 1 1 94 2 1 1 56 19 1 1 26 41 1 1 91...
output:
484.0000000000
result:
ok found '484.0000000', expected '484.0000000', error '0.0000000'
Test #17:
score: 0
Accepted
time: 1ms
memory: 4008kb
input:
1000 1100 488126101 731 610 585208088 540366708 561 62 86041805 368859358 831 710 211767264 781324566 74 980 63740672 108851121 434 524 401121183 304691309 322 227 381744909 617642887 130 614 915579616 289117241 251 787 461498291 80253760 550 370 559830063 373428962 629 839 710465667 338131414 205 5...
output:
199251332145721.3596191406
result:
ok found '199251332145721.3750000', expected '199251332145721.3750000', error '0.0000000'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
1000 1100 268733874 481 656 331185722 333159646 794 227 67131774 782107988 267 450 344511262 180544584 310 715 635839738 4152810 381 100 947088227 910798975 513 687 78786396 526240138 729 426 277710285 883234301 601 998 300659739 928886349 883 394 298648348 110449147 548 180 653034149 81362521 428 9...
output:
413201857755301.4225769043
result:
ok found '413201857755301.4375000', expected '413201857755301.0000000', error '0.0000000'
Test #19:
score: 0
Accepted
time: 2ms
memory: 4512kb
input:
2000 10000 556974939 1229 1241 775223317 818540310 1074 1694 991146337 51548755 1480 1695 222622016 735817516 1582 1950 855400049 911923207 249 810 908641618 810307433 1213 1111 709776557 975008490 793 1508 603053325 899489698 566 963 672550516 162012181 1067 1016 583117725 309308397 861 56 23862529...
output:
22951643164009.6182804108
result:
ok found '22951643164009.6171875', expected '22951643164009.6054688', error '0.0000000'
Test #20:
score: 0
Accepted
time: 0ms
memory: 4584kb
input:
2000 10000 504907784 1707 1722 906066363 251119348 1425 1330 552549489 863141392 1700 1479 547768258 504790397 27 1569 990936978 770266893 815 1734 518242893 570689786 496 1041 273723916 934280754 475 645 851848316 392819103 1709 1719 154453033 613106946 601 436 36146140 537470964 1121 538 978087967...
output:
97096823945.8443658873
result:
ok found '97096823945.8443604', expected '97096823945.8444061', error '0.0000000'
Test #21:
score: 0
Accepted
time: 0ms
memory: 4608kb
input:
2000 10000 4721617 1937 427 916035347 455169270 388 1219 530311691 486849191 1991 1544 213263909 716302642 1634 228 986072599 434310102 401 1745 671098166 728483547 43 2 632197398 855477488 721 692 296460133 21600055 1854 1414 750367136 846468804 1386 561 941169478 12455616 1234 1076 744141653 96645...
output:
1279988147198.0646418333
result:
ok found '1279988147198.0646973', expected '1279988147198.0644531', error '0.0000000'
Test #22:
score: 0
Accepted
time: 15ms
memory: 8692kb
input:
2000 100000 704418644 893 785 90556599 698901761 1045 1665 944458849 696241758 1387 1847 569166769 364833535 194 1591 700528586 62785104 1321 1800 478457217 152888199 392 1550 20987159 964850388 1810 1710 741333929 880773017 596 1513 965068252 167155121 152 1072 863004591 220229498 1086 970 56971539...
output:
984326987.1279412230
result:
ok found '984326987.1279413', expected '984326987.1279414', error '0.0000000'
Test #23:
score: 0
Accepted
time: 14ms
memory: 8916kb
input:
2000 100000 987488090 689 1861 606662099 746686468 1580 33 568223035 532236895 1401 1873 507680929 766651283 305 1667 620104510 639008035 1840 261 574236968 887953818 906 420 796727989 797425484 365 1298 679247996 946185064 1114 1648 965768480 949817365 1327 1613 665271340 878806906 1832 435 6788520...
output:
77044282066.1573776454
result:
ok found '77044282066.1573792', expected '77044282066.1573792', error '0.0000000'
Test #24:
score: 0
Accepted
time: 11ms
memory: 8712kb
input:
2000 100000 103649248 57 1497 873886032 519860594 1070 918 539422270 917061993 436 786 918425750 530236990 1930 608 625049473 760527878 33 1124 721476335 577957258 308 1945 640417192 766582115 1741 1824 834206496 576065447 692 842 802951112 822582179 1800 1120 976700275 691922524 383 821 820276486 5...
output:
1244424302266.5496282578
result:
ok found '1244424302266.5495605', expected '1244424302266.5498047', error '0.0000000'
Test #25:
score: 0
Accepted
time: 14ms
memory: 8688kb
input:
2000 100000 595886972 28 1505 923081742 532129841 759 256 600232175 656015109 500 1957 963371621 745482134 677 125 698449084 592476712 664 110 784394182 964897642 793 1035 891980288 766963116 575 808 531437588 589056220 1048 18 647692439 619119710 1375 1247 564666748 776224866 481 1980 876769545 835...
output:
274897766085.8658959568
result:
ok found '274897766085.8659058', expected '274897766085.8659668', error '0.0000000'
Test #26:
score: 0
Accepted
time: 14ms
memory: 8872kb
input:
2000 100000 259028375 1649 1694 770141366 717717568 337 1806 759783748 675008631 205 1849 911189377 617908961 476 1 631209825 825467763 991 1645 898051649 753805517 1900 1838 923710774 662420760 1193 1082 562088155 528940747 1362 1772 901669008 946521882 1193 1542 668703518 928561329 947 702 6429842...
output:
978543846685.7249616385
result:
ok found '978543846685.7249756', expected '978543846685.7248535', error '0.0000000'
Test #27:
score: 0
Accepted
time: 15ms
memory: 8476kb
input:
2000 100000 738451402 560 971 889038574 959945225 529 1480 143958551 291092150 1089 1796 523981044 880937075 713 1060 342946028 595506758 55 137 569847007 972986089 326 1975 312498014 515166588 145 1663 27083380 251459613 522 19 214348599 442440085 56 578 189191218 690374083 1648 866 9734788 9507875...
output:
120459109.3061793964
result:
ok found '120459109.3061794', expected '120459109.3061794', error '0.0000000'
Test #28:
score: 0
Accepted
time: 14ms
memory: 8464kb
input:
2000 100000 825377170 1612 178 997985036 635758691 960 773 675203125 772162403 937 634 501218623 772867194 543 1202 145997763 673935174 1199 1552 368463136 426649294 395 531 606065681 548937457 445 1105 607737256 370656954 519 1178 794779159 243642105 1443 1492 178348686 717900974 1410 1462 15756551...
output:
32850163.1957314642
result:
ok found '32850163.1957315', expected '32850163.1957315', error '0.0000000'
Test #29:
score: 0
Accepted
time: 2ms
memory: 4368kb
input:
2000 5000 978619771 925 246 699845935 995434620 1584 1574 928960594 994365519 197 151 585261269 830170752 1721 1718 486788595 352099644 1045 870 203508299 503766424 118 399 766811837 320098557 98 1768 290939503 571460042 673 168 551142460 492294046 1023 1867 412634795 811324427 1139 1032 547599216 8...
output:
1425612513.2726379375
result:
ok found '1425612513.2726378', expected '1425612513.2726383', error '0.0000000'
Test #30:
score: 0
Accepted
time: 10ms
memory: 7316kb
input:
400 79800 590452168 178 309 83361845 124207994 341 156 781480773 810785813 164 335 794788435 891550516 154 191 832083100 35520488 75 83 37798297 299935993 69 11 758490876 816402191 47 203 80564252 753284814 263 389 472510203 300172579 120 147 548575754 306531350 188 239 311155767 409336948 277 53 94...
output:
8509386.4877005002
result:
ok found '8509386.4877005', expected '8509386.4877005', error '0.0000000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
2 1 833022648 2 1 284347334 784133099
output:
267659176.7788383876
result:
ok found '267659176.7788384', expected '267659176.7788384', error '0.0000000'
Extra Test:
score: 0
Extra Test Passed