QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641659#9293. Fine TripCryingWA 1ms4364kbC++141.1kb2024-10-14 21:58:162024-10-14 21:58:17

Judging History

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

  • [2024-10-14 21:58:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4364kb
  • [2024-10-14 21:58:16]
  • 提交

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'