QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#564655#5145. Shortest PathnyctivoeTL 442ms254772kbC++174.9kb2024-09-15 12:12:372024-09-15 12:12:37

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5848kb

input:

4
3 2 10
1 2 5
2 3 4
3 0 1000000000
3 3 100
1 2 3
1 3 4
2 3 5
4 6 1000000000
1 2 244
1 2 325
1 4 927
3 3 248
2 4 834
3 4 285

output:

125
0
15300
840659991

result:

ok 4 number(s): "125 0 15300 840659991"

Test #2:

score: 0
Accepted
time: 2ms
memory: 5876kb

input:

400
4 7 850187899
1 2 83
1 2 24
3 1 23
2 3 80
3 3 65
1 2 55
2 4 31
4 7 297586795
3 4 54
1 1 66
2 2 75
1 3 68
1 4 27
1 4 29
2 3 96
5 7 217277444
3 3 9
3 4 36
2 2 77
5 5 38
3 3 6
1 2 18
1 2 23
5 6 379032278
5 5 96
4 3 92
3 2 49
4 3 44
1 4 19
1 1 18
5 6 534284598
5 1 59
1 2 2
3 3 55
2 2 24
5 4 34
2 4 7...

output:

191476186
406722183
0
0
58483482
115858544
177378789
656019644
858116309
0
38761681
633010531
0
696693112
919354187
122684249
865793975
91541737
248634956
0
374201737
455984810
284991806
322357914
0
514668426
407812429
555256220
0
419773408
989291360
743372489
0
716008724
0
189418326
244106015
41273...

result:

ok 400 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 5812kb

input:

400
4 6 415388949
4 2 6853
4 3 5541
1 2 6273
4 4 8561
4 1 9638
4 2 8341
4 6 195566032
2 3 6344
1 1 7616
3 1 4823
4 1 647
4 4 7091
4 2 6307
4 6 720662513
3 3 4435
2 1 4448
4 3 3142
4 1 6670
2 4 5545
2 3 2990
5 7 806244066
3 2 3989
4 3 8157
5 2 612
3 5 8294
1 1 2114
3 4 2311
5 2 8825
5 6 894954332
4 1...

output:

392283147
970308579
491899881
0
495762954
10156057
664457753
0
575852185
134843393
933754264
590740253
0
490859785
724017823
957609109
0
622353894
279038091
426991125
0
637389724
0
75171267
749597224
258493187
250907837
497917111
886569508
828505392
68793449
224109727
139499076
786372001
894480753
4...

result:

ok 400 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 5892kb

input:

400
4 6 626798206
4 4 835705
3 2 236950
2 4 952235
1 2 581609
3 2 204788
2 1 947505
5 7 121450775
2 2 288007
3 2 130288
5 4 76431
4 5 23594
2 5 675316
4 1 192066
3 3 275296
5 7 867412084
1 4 473530
4 3 242225
2 3 459428
2 2 852747
4 1 242292
1 2 9788
3 2 175026
5 6 270426492
5 4 75346
4 2 880851
5 2...

output:

359593563
746525185
0
0
73714485
664197694
720306834
414192169
852090104
263236207
112963474
326265087
32838160
575302262
917139513
704934710
717038510
608349067
804139086
30761395
0
885174847
903442468
235788993
315187893
267383762
881704492
392427980
511540414
82510129
841018587
628947824
90374582...

result:

ok 400 numbers

Test #5:

score: 0
Accepted
time: 2ms
memory: 5888kb

input:

400
4 7 237940126
2 3 811465519
3 1 406242509
4 2 568535949
4 4 916500298
3 2 79853489
2 4 485382745
2 3 421622532
5 6 680552144
5 4 315694734
4 1 414031567
5 4 530765372
2 5 734798151
4 5 677388912
3 2 511925895
4 6 174169143
1 2 355579133
1 1 374390087
3 3 393590012
2 3 72192607
1 2 898660531
3 1 ...

output:

80828666
371586866
0
167800461
410107945
445437334
0
610069154
796266829
467729673
259462318
581867042
658714588
354982099
590749802
487914460
0
115063504
426498590
124790015
0
408391987
0
108209715
16338078
814297806
454529244
185281507
453042901
940987029
353015051
435087926
0
0
246967770
0
929531...

result:

ok 400 numbers

Test #6:

score: 0
Accepted
time: 2ms
memory: 11952kb

input:

40
46 100 796871833
14 45 5
34 15 75
18 35 36
18 24 62
7 36 17
17 9 45
31 33 11
33 15 34
23 5 72
23 27 44
16 15 3
10 28 18
1 36 89
4 40 32
46 43 55
14 22 61
30 15 36
8 2 82
21 12 15
42 45 78
26 40 11
46 32 42
26 46 10
39 40 83
37 39 95
45 27 45
32 37 91
2 19 34
9 7 74
28 5 99
3 44 34
33 38 6
18 13 7...

output:

486700134
857700687
608672173
864577567
889360467
813527860
503310571
949592684
427562681
54612131
295765111
981822742
297387832
510195726
183427910
339067217
163331381
781441071
387001805
800276039
215789954
315236685
325091800
561623521
0
564200504
58828620
705573545
860792488
149660643
968795549
...

result:

ok 40 numbers

Test #7:

score: 0
Accepted
time: 3ms
memory: 14272kb

input:

40
49 98 637035062
28 11 4294
36 2 7586
44 33 6870
19 3 4054
38 5 2009
2 26 6184
5 45 2951
33 23 7022
18 38 3008
46 19 8137
49 18 6080
18 37 8209
18 8 9077
31 43 6509
42 22 5743
2 18 9127
16 2 8584
38 11 7504
15 12 2867
1 19 8063
11 26 9017
17 3 6127
23 19 5473
13 38 4521
25 37 7360
31 34 6656
47 22...

output:

821693058
71016907
857321273
783587298
982610065
980278015
275485521
971090373
233315886
399922806
0
278608644
378866648
599249221
340396754
540768603
530594607
776205772
730857174
933810552
227365258
382149558
937071245
521975672
690097593
73883754
33862436
462058733
443441774
438932117
64257634
58...

result:

ok 40 numbers

Test #8:

score: 0
Accepted
time: 5ms
memory: 12300kb

input:

40
46 95 723931456
35 20 947776
31 38 238603
37 17 836768
12 40 35931
25 6 38152
17 27 195009
37 26 230999
2 12 963773
22 18 283748
9 34 499029
30 9 601767
38 4 966623
21 3 740901
32 31 66189
9 46 751585
38 27 412857
40 28 136769
2 17 118003
21 18 102142
45 31 319817
33 13 496656
16 5 168278
37 15 9...

output:

862261239
934208524
676535904
425060961
680809878
921710894
166137599
490099382
786664556
667359023
117551032
65363912
805410419
453568705
636903494
876708711
0
874460066
688545496
770335168
196141613
286072255
826782785
385627101
487670842
692193056
921891801
493485960
746027697
94281264
761466453
...

result:

ok 40 numbers

Test #9:

score: 0
Accepted
time: 5ms
memory: 12072kb

input:

40
50 90 857563025
2 11 393746492
45 46 345072720
13 18 637861512
47 3 571609922
50 35 402605542
23 36 161663167
27 20 267096312
50 47 967313350
6 23 797326121
12 47 19611590
32 22 693454539
6 40 749059549
14 47 655748726
9 32 774397775
49 22 471626653
18 23 775770441
8 47 263012466
17 27 714895319
...

output:

823474705
897491227
830605997
310507990
396608942
755858403
192083730
558837131
397169944
133851804
124398473
334337729
676169091
498313169
10613351
887468199
938570424
730866390
93748497
991959257
969327421
950615046
29589899
290773789
436801411
468797561
311350228
807413343
196500651
737421403
330...

result:

ok 40 numbers

Test #10:

score: 0
Accepted
time: 64ms
memory: 66324kb

input:

4
452 997 787553451
224 333 31
99 434 28
63 105 64
15 304 41
43 356 18
359 280 70
446 415 69
256 296 47
276 108 23
138 249 8
152 281 31
284 122 45
1 10 39
348 216 4
260 386 51
442 340 3
305 316 81
103 267 18
444 14 16
418 221 20
366 343 72
448 265 44
419 417 60
433 251 19
138 373 42
221 251 52
219 2...

output:

920051934
337790394
379237832
857209587

result:

ok 4 number(s): "920051934 337790394 379237832 857209587"

Test #11:

score: 0
Accepted
time: 70ms
memory: 67880kb

input:

4
488 933 522189685
296 341 4432
469 325 7333
230 83 8870
61 45 9898
236 85 6295
90 304 7287
486 400 6268
115 485 7251
455 214 9376
74 402 2519
461 119 4761
379 238 966
235 139 5469
365 82 5901
143 101 4371
110 323 8173
126 186 9270
451 315 9574
340 282 2321
152 360 7030
112 317 3895
388 484 1202
21...

output:

603678306
943491463
173268290
201396620

result:

ok 4 number(s): "603678306 943491463 173268290 201396620"

Test #12:

score: 0
Accepted
time: 79ms
memory: 68000kb

input:

4
475 925 862065786
223 259 326692
311 176 146944
236 82 519523
454 402 81050
314 40 916288
147 431 876771
457 438 621257
400 157 931920
22 170 696985
236 219 335364
229 83 709348
238 112 98295
284 436 112450
38 119 757155
256 275 92474
194 116 661424
306 15 548944
308 426 87714
9 203 246801
288 448...

output:

0
700852946
806811784
955695134

result:

ok 4 number(s): "0 700852946 806811784 955695134"

Test #13:

score: 0
Accepted
time: 62ms
memory: 67928kb

input:

4
468 943 401471037
16 76 84807660
391 15 339856779
217 269 160461855
105 400 445538323
90 401 136863755
23 152 971192392
51 339 208461283
467 55 188586800
61 65 493966321
140 229 716542747
182 270 337275222
154 76 601108616
377 254 684327428
103 375 734134843
327 225 26827769
26 248 368659099
457 5...

output:

158572391
663760343
713171553
450639895

result:

ok 4 number(s): "158572391 663760343 713171553 450639895"

Test #14:

score: 0
Accepted
time: 442ms
memory: 254772kb

input:

1
1967 4772 636170050
1469 497 29
698 1900 25
1731 103 98
1190 812 60
1066 904 32
569 223 41
1263 1625 89
300 483 43
422 734 52
229 88 58
1319 1391 15
1684 71 83
1306 789 98
288 1736 43
269 1183 72
696 707 10
1439 55 18
159 356 11
1901 17 82
1143 1004 14
1792 1663 29
1240 1515 66
548 1911 79
1554 14...

output:

12502270

result:

ok 1 number(s): "12502270"

Test #15:

score: 0
Accepted
time: 380ms
memory: 233568kb

input:

1
1802 4503 646877183
1127 984 7603
556 882 5723
127 507 7174
433 370 2556
39 1516 9375
334 805 1773
341 55 8686
1570 1207 2941
13 306 2050
1080 752 1702
197 663 1476
1137 1426 3546
568 127 7250
1442 171 223
979 48 4046
556 1172 6317
1293 452 3992
1439 296 4087
1783 529 6601
773 1796 3624
198 324 81...

output:

273339035

result:

ok 1 number(s): "273339035"

Test #16:

score: 0
Accepted
time: 416ms
memory: 246784kb

input:

1
1904 4785 968128956
859 417 113491
403 1270 191589
129 1812 622246
1270 1381 15261
879 1580 307339
431 1471 63479
812 1707 636114
1078 1600 402010
125 150 168133
1551 962 517476
1341 82 13938
691 1085 223701
1567 1596 985654
1196 1792 196604
113 1335 773004
948 1566 912289
1811 1804 809238
1344 94...

output:

774302007

result:

ok 1 number(s): "774302007"

Test #17:

score: 0
Accepted
time: 414ms
memory: 245432kb

input:

1
1905 4762 791011485
308 1642 674031390
170 417 451432236
668 1138 975582181
13 559 257035921
225 658 268340515
111 488 381378525
397 2 542379808
395 956 690894704
687 390 942311067
1257 1140 945365111
105 1789 545765059
393 1382 996273411
620 1639 137431157
126 1252 713096043
908 923 621490871
120...

output:

311528206

result:

ok 1 number(s): "311528206"

Test #18:

score: -100
Time Limit Exceeded

input:

400
4 7 99
1 2 83
1 2 24
3 1 23
2 3 80
3 3 65
1 2 55
2 4 31
4 7 95
3 4 54
1 1 66
2 2 75
1 3 68
1 4 27
1 4 29
2 3 96
5 7 44
3 3 9
3 4 36
2 2 77
5 5 38
3 3 6
1 2 18
1 2 23
5 6 78
5 5 96
4 3 92
3 2 49
4 3 44
1 4 19
1 1 18
5 6 98
5 1 59
1 2 2
3 3 55
2 2 24
5 4 34
2 4 79
4 7 93
3 3 75
3 3 32
3 4 89
1 1 6...

output:


result: