QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#641659 | #9293. Fine Trip | Crying | WA | 1ms | 4364kb | C++14 | 1.1kb | 2024-10-14 21:58:16 | 2024-10-14 21:58:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef array<ll,2> pr;
const int N = 2010;
const db INF = 1e23L;
template<typename T>void tomin(T& x,T y){x = min(x,y);}
template<typename T>void tomax(T& x,T y){x = max(x,y);}
//
int n,m,T;
vector<pr> e[N];
db dis[N]; int inq[N];
queue<int> qu;
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m>>T;
for(int i=1,u,v,x,y;i<=m;i++){
cin>>u>>v>>x>>y;
e[u].push_back({v,1ll*x*y});
e[v].push_back({u,1ll*x*y});
}
for(int i=1;i<=n;i++)dis[i] = INF;
for(auto [v,w] : e[1]){
tomin(dis[v],(db)w);
if(!inq[v])qu.push(v),inq[v] = 1;
}
while(qu.size()){
int u = qu.front(); qu.pop(); inq[u] = 0;
for(auto [v,c] : e[u]){
db p = sqrt(dis[u]),q = sqrt(c);
db w = (dis[u]*q + c*p)*(p+q)/p/q;
if(w < dis[v]){
dis[v] = w;
if(!inq[v])qu.push(v),inq[v] = 1;
}
}
}
db ans = dis[n] / T;
printf("%.6Lf\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3924kb
input:
3 3 100 1 3 100 100 1 2 100 24 2 3 100 24
output:
96.000000
result:
ok found '96.0000000', expected '96.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
3 2 10 1 2 9 1 2 3 1 1000
output:
119.873666
result:
ok found '119.8736660', expected '119.8736660', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4056kb
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.147811
result:
ok found '4.1478110', expected '4.1478114', error '0.0000001'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3936kb
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.419533
result:
ok found '1150229105.4195330', expected '1150229105.4195333', error '0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4116kb
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.964239
result:
ok found '2496450976.9642391', expected '2496450976.9642396', error '0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4188kb
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.353026
result:
ok found '4087930881.3530259', expected '4087930881.3530254', error '0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4060kb
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.125570
result:
ok found '38723.1255700', expected '38723.1255704', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4000kb
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.814496
result:
ok found '12841383894.8144951', expected '12841383894.8144989', error '0.0000000'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4052kb
input:
4 4 964438192 2 4 216592581 216592586 1 2 216592587 216592580 3 4 216592587 216592580 1 3 216592582 216592585
output:
194568600.108713
result:
ok found '194568600.1087130', expected '194568600.1087127', error '0.0000000'
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 4364kb
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:
1147535033355228.684326
result:
wrong answer 1st numbers differ - expected: '2809268677693535.0000000', found: '1147535033355228.7500000', error = '0.5915182'