CT65175

The Gleaming bridges of Freya

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the forest village of Briarthorn opens only for a perfect tally of bridges. Freya means to find out. 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 <= 820; 0 <= m <= 2460; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 660 1498 1 660 152 411 709022 27 578 154278 70 557 732615 151 266 466723 312 542 560680 44 634 823630 178 571 348790 9 41 117379 418 578 783156 285 495 340581 428 566 652362 312 608 831333 613 621 317585 233 651 818328 84 560 272490 638 642 3009 442 559 688119 242 541 731196 336 520 294017 121 658 201849 599 612 717038 192 575 842313 184 373 493246 45 511 20485 402 430 164473 241 473 510859 199 364 800433 375 455 285533 86 567 941650 69 222 132223 392 562 9826 453 652 674194 431 470 701808 120 627 800191 361 617 542793 288 425 411122 12 640 882886 27 175 759438 33 454 447623 204 330 123296 130 632 256672 265 616 201138 58 630 854011 392 424 677587 365 645 823591 248 271 456713 516 625 998571 204 245 229814 389 564 997750 383 491 786518 377 382 275176 138 498 651392 401 553 54060 634 636 10…
Output: 1781809

Example 2:

Input: 608 1258 1 608 389 495 577684 230 599 860249 68 206 708134 195 549 725321 96 401 577518 104 292 494794 184 253 201881 387 489 620619 67 106 738525 3 256 301183 203 263 331277 472 585 139183 160 393 251073 137 597 632278 1 551 559859 341 435 641704 143 294 240322 87 312 172448 329 398 132635 124 551 208074 163 221 183267 414 482 768789 471 539 734179 154 301 434473 229 379 807545 312 395 277335 275 276 440209 479 537 327387 355 522 792265 130 201 714179 35 606 981400 363 583 79878 410 478 917491 340 535 869199 138 264 407907 501 548 550922 110 277 83004 314 374 881372 132 157 497586 110 522 986631 143 167 408495 319 366 99110 28 585 405933 144 324 450074 21 583 211313 268 377 295756 523 600 383893 422 566 960321 163 470 361285 115 230 199168 339 529 640658 121 361 699996 177 347 647500 292 …
Output: 1002161

Example 3:

Input: 810 1060 1 810 314 517 706381 619 719 347206 29 191 634413 352 474 490587 219 450 205809 413 745 153661 387 486 611544 172 327 350807 417 664 509882 241 659 875910 611 799 380856 160 798 254284 155 559 210833 68 70 296652 115 445 215325 175 459 609027 431 483 134674 380 421 763390 65 716 667457 414 784 682810 202 431 988564 258 289 268783 590 738 920064 382 765 697454 25 799 802497 53 266 388661 335 806 735999 158 165 483820 50 294 808248 175 347 467100 388 474 9879 53 487 907106 63 317 828327 629 689 469283 625 690 435053 85 703 258528 38 481 522952 458 511 829190 256 350 615569 79 404 90814 31 658 423309 481 666 397064 279 530 800056 189 657 156383 199 385 112497 42 487 789701 566 581 218588 625 651 239799 532 618 136883 163 643 25428 108 752 621178 532 648 597357 182 375 735916 84 728 8…
Output: 3459158

Constraints:

1 <= n <= 820; 0 <= m <= 2460; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Loading...
Test Cases:No test cases
No test cases available.
The Gleaming bridges of Freya - MEDIUM Coding Problem | CodeTikki