CT58519

Koda and the Lazy canals

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Koda inherited the apothecary at the honey farms of Buzzwell along with its curious bookkeeping system for canals. Time to make sense of it. 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 <= 1666; 0 <= m <= 4998; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 644 2438 1 644 32 156 30 5 55 948 291 496 71 482 613 629 12 543 462 425 563 982 294 453 943 396 571 822 198 246 54 81 326 232 202 383 134 103 359 707 121 261 864 269 367 876 180 513 792 84 535 710 50 569 161 19 480 726 41 187 231 193 252 754 193 411 452 416 607 223 276 525 122 258 620 433 8 620 46 395 476 376 135 469 335 74 290 694 87 439 681 387 451 120 170 528 736 24 338 199 438 611 507 114 433 232 68 259 345 382 517 39 58 201 744 226 363 589 280 292 107 358 386 424 328 500 583 45 473 321 317 566 310 235 368 265 31 340 881 215 543 23 73 190 986 48 462 772 609 643 912 39 77 433 146 243 885 275 314 872 11 44 348 86 197 248 222 364 457 200 247 904 239 584 598 49 65 670 157 276 193 107 343 551 55 178 806 25 644 429 433 554 49 199 344 115 195 423 14 246 480 824 26 398 754 86 613 331 194 589 4…
Output: 322

Example 2:

Input: 352 3252 1 352 155 277 882 217 243 566 21 86 58 141 188 156 80 83 257 219 250 688 1 259 545 65 282 243 280 290 311 52 322 918 179 224 876 30 163 783 16 297 850 104 289 793 177 249 546 25 280 280 151 187 245 225 286 391 133 208 790 222 259 488 11 280 220 92 243 927 119 209 970 22 288 633 228 233 729 143 318 225 23 275 547 34 103 97 184 330 120 36 130 550 120 350 587 100 134 354 87 104 541 9 320 355 140 169 959 123 208 284 180 219 109 53 320 953 213 238 509 189 337 458 50 103 270 169 319 25 37 273 182 4 159 287 100 162 480 64 72 91 236 339 262 108 248 957 103 320 762 130 329 453 190 238 999 58 237 120 180 315 969 53 198 843 171 344 882 236 350 343 90 302 894 29 30 81 189 190 423 19 67 411 240 320 388 94 219 611 143 228 558 216 225 788 82 242 372 97 159 483 212 281 954 270 293 571 283 287 334…
Output: 258

Example 3:

Input: 1510 2616 1 1510 513 615 559 893 1457 942 80 345 317 999 1339 402 46 1352 753 592 1004 1 84 481 575 326 636 973 481 1088 763 1056 1496 635 346 778 52 610 1196 503 84 861 538 546 683 521 318 369 576 186 197 740 186 1026 842 507 1151 261 1277 1433 93 229 921 81 1166 1333 202 264 1095 157 125 417 149 1104 1364 329 352 1413 35 1061 1319 416 436 567 876 179 637 810 16 235 822 530 1182 906 271 1171 232 702 1157 11 593 918 198 340 745 189 96 242 143 1019 1094 620 1031 1252 369 584 695 883 290 997 854 867 1453 290 553 885 820 644 793 653 731 1002 22 78 280 974 163 263 665 1323 1467 700 492 1439 96 689 703 993 218 602 280 619 674 845 614 1197 932 284 1171 334 563 1201 547 781 1234 499 449 472 540 616 1009 453 751 1260 791 189 844 222 269 1323 126 1231 1347 560 82 1373 393 481 935 57 460 586 396 396…
Output: 3441

Constraints:

1 <= n <= 1666; 0 <= m <= 4998; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Loading...
Test Cases:No test cases
No test cases available.
Koda and the Lazy canals - MEDIUM Coding Problem | CodeTikki