CT42180

Dora's Teal Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the salt flats of Palemere. Dora spreads the bridges records across the table and picks up a sharp pencil. Task: An undirected weighted graph is given. Print the shortest-path cost from s to t, or -1 if unreachable. Input format: First line: n m s t. Next m lines: u v w. Output format: Print the shortest distance or -1. Constraints: 1 <= n <= 1001; 0 <= m <= 3003; 1 <= s,t,u,v <= n; 0 <= w <= 1000000000; distance fits 64-bit.

Example 1:

Input: 216 2378 1 216 115 164 537305009 70 110 359085096 19 111 705322139 42 65 684743647 97 211 355355026 109 193 894854972 121 204 149784866 128 142 189813757 45 126 806816877 15 164 177349743 1 124 209535268 80 116 458704797 88 163 156748841 12 52 40351350 49 183 569204572 44 112 603052373 9 140 724421588 1 162 380206014 30 40 281552605 88 112 268131253 92 199 211175886 200 212 831834279 55 115 242982788 142 201 990045559 40 143 508108797 57 63 895494323 68 211 675098789 75 117 561124653 144 203 664248838 48 216 995671721 69 127 971641803 115 197 999017439 57 216 388778839 50 105 723347045 185 195 437216409 140 158 805056725 84 127 190620305 20 216 833975008 4 11 746930990 35 50 61260047 116 150 6802557 63 171 222419033 157 206 423666300 47 161 164050987 84 139 104045226 117 134 71345574 7 124…
Output: 197216704

Example 2:

Input: 215 2422 1 215 21 97 914263262 50 155 850009609 17 116 140468686 8 93 94975590 3 81 240434058 86 127 850574269 24 142 482937068 78 162 644222268 10 170 549365822 130 158 650634720 100 160 802128776 97 111 69756722 168 203 139603619 72 143 40962384 22 39 604019883 29 187 13048684 129 146 255103423 96 209 7206 65 136 903790297 82 179 526578641 6 94 888711126 43 133 882472728 136 182 773731042 61 69 522611065 94 188 504575290 171 180 31149510 207 214 985099520 85 200 659692357 85 104 922288316 173 202 305675434 110 117 369626321 136 149 289358068 122 168 308188469 20 131 920066788 23 164 643960899 43 154 825610308 29 65 537497255 101 184 360899575 108 131 827738285 51 78 575614105 128 185 291732460 22 151 583473927 69 208 241727747 76 211 489728054 30 85 915684302 84 95 124910517 50 163 40167…
Output: 355902313

Example 3:

Input: 885 1405 1 885 192 835 845646618 84 93 601932413 131 572 104436095 90 604 89443689 272 365 293532782 255 398 991063522 293 621 15630452 81 630 121342345 252 358 211405153 690 783 608740198 176 873 869813275 364 619 512571574 529 559 911531493 211 242 812348038 4 534 17174179 131 353 607269526 23 706 476032367 639 696 873023899 176 342 117175469 402 835 977328725 64 333 382111024 842 846 372431524 281 438 147990640 553 850 729069021 124 151 560505894 102 612 952793208 537 553 294488862 189 339 241315426 676 679 715559774 252 605 36718278 69 862 148270582 296 729 705762134 720 771 402949593 130 416 250431230 24 124 829040507 25 813 581166290 419 691 385132433 205 247 31602947 530 689 934852307 458 574 465695425 77 801 661493118 56 74 887040370 3 248 488921614 99 387 794421149 258 574 3096446…
Output: 3847251287

Constraints:

1 <= n <= 1001; 0 <= m <= 3003; 1 <= s,t,u,v <= n; 0 <= w <= 1000000000; distance fits 64-bit.

Loading...
Test Cases:No test cases
No test cases available.