CT64110

Lakshya's routes Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the crane marshes of Stillwater. Lakshya spreads the routes 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 <= 1109; 0 <= m <= 3327; 1 <= s,t,u,v <= n; 0 <= w <= 1000000000; distance fits 64-bit.

Example 1:

Input: 118 1432 1 118 51 108 511528028 3 21 435348647 8 75 326092551 21 51 348449709 19 52 715353969 45 58 339079237 63 109 568794468 14 89 969509319 17 60 15713478 12 92 252265109 7 75 754719594 45 100 270424138 24 60 421808875 31 95 970689281 18 64 740179043 85 101 671856560 64 70 726440758 61 107 153849323 12 79 400726009 92 104 246795079 72 110 657139686 2 64 115905839 32 99 117453547 12 85 582063272 28 48 258154375 30 66 990783268 42 55 915471284 31 36 665341222 75 92 407591739 37 67 145403069 56 118 894063939 71 97 795464271 33 70 491380605 5 88 736851597 31 51 958176736 71 76 537237134 103 104 246116457 2 28 26863196 12 110 225275786 14 101 61310908 18 31 462017124 50 59 214717308 74 110 844244481 39 76 67384702 8 94 689702389 105 109 838446472 7 18 34754401 16 96 342620373 93 96 86457438 …
Output: 195741573

Example 2:

Input: 437 3074 1 437 22 330 633691755 2 45 386525980 167 406 111798971 99 282 661984782 170 182 559528045 315 349 999581755 22 321 635526631 197 428 850943682 244 427 679869003 101 296 896328566 209 282 166423323 394 407 921317281 312 361 123694 46 268 556611801 19 104 936710967 81 123 881036457 159 236 467795232 206 295 692076723 221 228 592876026 167 410 516951954 177 298 559600821 399 437 593593944 71 415 817451009 286 361 526345657 126 423 656250649 114 172 730706204 284 377 32042279 115 152 925003913 104 146 426224475 381 387 824202265 71 353 668506508 237 272 410897842 34 165 365352757 204 361 805246535 27 171 206865027 389 431 147037109 60 210 643864031 71 262 914167517 162 422 520746476 22 107 28033963 33 302 98853883 76 148 263105528 253 262 3738546 241 361 507058458 40 136 461835397 56…
Output: 397026139

Example 3:

Input: 783 782 1 783 536 543 640922976 102 257 745719902 188 261 130705793 25 443 301105913 76 618 94166087 273 773 241490099 175 513 80400249 35 601 498124357 194 335 793320610 11 216 67807497 113 224 995811928 101 479 862432323 581 680 931975128 363 471 141110009 86 726 36521926 404 480 326423368 93 394 540217198 383 672 510538869 188 524 71407132 433 632 276970754 382 392 502045457 576 630 46061899 348 676 779590063 271 429 203405095 163 591 212874570 640 675 160888777 246 676 688408090 87 133 604462317 375 605 878871128 485 633 394756151 193 297 356166553 263 468 114598980 286 493 374564412 109 413 5974529 407 702 791465709 331 528 378101441 95 696 602402574 426 578 776307056 57 580 808979128 160 388 507484854 319 575 729512197 432 665 587954156 244 266 479468924 87 557 326283621 188 499 3358…
Output: 5440284740

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Lakshya's routes Reckoning - MEDIUM Coding Problem | CodeTikki