CT64016

Last routes of Jaya

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the pine barrens of Needlepoint as Jaya unrolls the day's manifest of routes. The tally will decide the next shipment. 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 <= 1390; 0 <= m <= 4170; 1 <= s,t,u,v <= n; 0 <= w <= 1000000000; distance fits 64-bit.

Example 1:

Input: 995 3055 1 995 804 958 913420890 598 988 539612161 736 882 102311621 609 717 197531320 455 752 54005322 232 525 852120894 3 83 916844524 187 770 397862071 162 968 462658372 469 962 424107932 490 631 788254948 119 655 913719582 261 776 183628122 540 606 132553244 287 345 636922440 308 423 804389877 201 948 353766872 584 654 982806425 749 884 183227891 911 972 452301392 81 130 940424768 365 851 686663708 622 742 846186395 862 932 161990204 155 517 566805560 646 883 106627047 288 846 495543452 200 833 248584706 136 224 562429286 57 619 551482727 137 216 271948213 215 422 36328941 290 616 127601903 682 867 736596791 76 636 38813424 486 941 514080975 642 814 509871040 245 586 325519526 649 704 798143208 141 780 616184822 293 734 167614852 80 165 111793065 408 528 592605087 412 804 703155120 162…
Output: 931332820

Example 2:

Input: 163 300 1 163 103 117 884788624 77 104 372227042 121 160 340423930 77 154 491209348 94 132 28464974 59 91 494203446 65 163 722504104 18 125 346127427 75 123 425710522 46 124 135743237 97 111 111679435 27 65 622723253 18 96 581550868 37 99 937606631 15 85 90549760 35 62 144907167 62 104 193878956 37 127 619992563 88 125 357139207 47 156 12420123 36 97 801321068 16 45 824039347 25 161 651033993 61 120 887048888 3 39 890084739 17 92 555821011 4 84 631657972 125 161 256850510 110 134 40985237 72 104 16315964 2 82 330655677 31 56 390892451 135 153 824928507 66 115 531810732 13 149 171160041 92 162 777967599 40 108 715487758 55 113 346071414 73 90 503685447 94 159 361232026 28 153 156828291 43 146 271428546 58 99 369511257 95 120 732201947 22 134 42482036 1 88 412056534 41 82 446489340 76 147 64…
Output: 2730146492

Example 3:

Input: 398 2183 1 398 23 67 56513120 71 321 492816548 17 345 380859215 24 117 571510211 141 175 21955090 25 306 546591602 90 225 504147402 164 319 305781532 311 312 726875360 216 335 230019655 71 210 389842607 153 204 624050943 208 326 741329682 23 37 215686244 210 374 984168333 119 131 922944247 85 389 473942331 349 388 575383837 71 345 133216045 196 324 686892564 43 389 492292200 154 202 270398293 202 293 680622311 46 346 394135798 101 139 236172612 164 211 763034150 246 370 130774671 234 247 197757219 42 75 56481718 17 349 916398050 136 310 938416085 38 57 607033920 178 311 422183140 247 302 556404066 245 344 285881394 149 237 366043155 220 237 609089026 70 241 883524823 170 297 192927901 220 309 622518286 41 84 403335668 373 398 793713264 298 334 862381498 284 334 766292239 166 257 229732032 …
Output: 421741314

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Last routes of Jaya - MEDIUM Coding Problem | CodeTikki