CT53046

Jeweler and the Fastest Route

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the lakeside town of Mirrormere, someone must prepare the guildmaster's brief. This year the task falls to Jeweler, armed only with the routes register. 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 <= 1153; 0 <= m <= 3459; 1 <= s,t,u,v <= n; 0 <= w <= 1000000000; distance fits 64-bit.

Example 1:

Input: 535 2490 1 535 140 532 540149326 456 494 358744699 301 422 611839419 290 328 774946112 302 428 255349501 214 286 196280983 155 526 580718652 426 489 388300108 6 251 485213536 72 285 641547895 250 311 754300574 408 524 538646977 247 431 480543635 211 270 966958862 237 453 205598365 45 201 99690267 292 528 356719426 151 331 659459187 97 353 943430294 127 535 179511268 23 150 411388562 196 334 175714311 39 442 815798410 77 122 107884395 123 171 971730137 189 312 974993165 47 364 973239800 105 285 486154291 3 483 873255646 259 443 572967986 352 476 176159713 54 532 865950098 237 425 611151723 86 119 593578737 153 270 767757803 54 529 986268253 251 399 19229528 311 376 396689779 112 244 770000311 80 248 809613052 109 443 478691162 235 449 850344207 126 508 144751769 96 380 808733244 30 65 16594…
Output: 590798771

Example 2:

Input: 962 961 1 962 417 939 622131028 489 874 343107651 395 436 749454434 738 791 540115446 404 466 668501935 205 424 474865661 632 657 19468180 310 743 544065988 44 555 36241578 107 570 843483526 220 271 303098154 641 703 368808206 289 844 715262529 441 794 693007306 694 804 973139936 730 858 776837896 456 685 93838735 639 685 672288713 232 492 156475041 82 774 719978838 341 688 594614968 488 702 928610852 309 679 359530772 870 911 648131867 532 842 10476220 418 572 550103542 842 895 203792734 544 719 52064847 31 502 758374593 404 446 364420256 185 485 214279510 189 487 940764884 180 714 611580695 204 957 237297944 55 478 851200151 355 404 915329654 24 762 637707852 120 785 33289357 490 737 197741117 826 881 369899654 258 956 369836182 55 772 155632153 179 752 806046279 619 932 818972359 440 44…
Output: 6275251943

Example 3:

Input: 716 2009 1 716 434 656 925157172 414 421 38830302 126 543 943778844 210 543 440016319 56 519 828534235 327 389 728784644 183 263 676121962 342 674 705297909 183 236 391198982 339 576 785848260 220 343 144189393 384 617 119940349 221 273 942353096 539 543 970623544 14 105 102943032 479 527 925781875 105 677 504165744 568 678 228008442 341 713 45578961 241 562 857626711 144 287 867147144 449 585 729774785 69 286 861350956 145 319 780820246 85 453 677500273 275 690 833532231 197 539 687316953 475 696 77736561 464 550 591610879 133 155 188120544 66 121 781023289 44 51 461808881 606 675 61250307 137 429 35559541 137 269 569031499 337 544 939388292 472 554 303983827 191 639 343473908 453 537 664658072 130 541 241625296 143 235 480152902 303 372 558970390 225 233 279438723 174 176 741270760 353 5…
Output: 1710233225

Constraints:

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

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