CT48233

Last canals of Xavi

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Xavi found an old ledger of canals in the depot attic at the river town of Willowford. The margin notes pose a precise question. 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 <= 1014; 0 <= m <= 3042; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 35 37 1 35 3 4 940 18 31 529 4 30 866 3 35 290 5 26 201 25 34 819 13 27 416 18 27 527 19 30 816 2 12 747 25 27 281 13 29 209 28 30 396 11 17 181 3 27 772 8 27 103 3 33 328 11 25 913 5 31 537 6 25 469 7 22 307 10 21 2 18 24 616 23 28 521 18 32 354 1 7 597 5 20 870 1 11 675 9 21 934 9 19 500 22 34 102 4 15 705 2 27 32 21 24 483 21 31 131 14 29 392 16 27 275
Output: 2931

Example 2:

Input: 384 383 1 384 166 377 799 143 285 209 6 211 495 199 284 293 163 335 66 42 241 849 299 323 374 248 343 519 67 378 746 210 292 179 36 180 789 133 140 258 222 244 982 132 254 117 3 273 731 265 326 959 146 291 342 314 380 339 27 289 365 163 358 919 12 36 865 219 278 58 85 192 371 30 44 215 53 127 996 206 270 720 300 335 331 130 301 978 132 238 300 250 254 871 62 284 537 258 312 635 58 70 22 117 347 896 165 259 221 112 145 214 58 118 606 83 184 195 153 328 521 176 297 984 78 369 603 41 67 808 57 217 793 38 195 809 157 224 833 59 283 321 237 363 852 124 267 61 222 301 598 29 292 304 38 174 269 256 285 461 10 366 233 93 334 311 304 347 136 58 183 59 342 382 652 196 343 647 226 352 447 277 376 958 56 182 85 83 191 763 50 167 535 5 164 34 190 287 919 138 320 147 132 257 859 106 150 55 138 207 652 8…
Output: 5390

Example 3:

Input: 620 832 1 620 16 435 26 120 179 550 233 474 141 154 495 379 289 618 221 55 167 260 271 390 801 326 562 172 465 542 410 49 610 496 395 465 479 426 443 78 173 376 441 275 448 447 412 515 54 142 515 674 526 598 502 203 216 861 577 587 151 14 91 678 33 269 327 324 516 728 425 525 691 328 505 623 5 357 274 198 235 916 51 582 969 532 594 130 286 321 578 439 513 666 84 245 762 150 285 305 177 394 869 302 386 902 382 401 614 224 472 180 87 419 912 237 457 733 532 585 263 316 372 897 49 614 459 61 184 743 98 402 717 51 310 45 153 619 823 29 349 616 244 559 87 574 588 53 130 227 635 166 318 26 170 212 782 428 467 80 172 497 135 205 564 518 325 425 982 211 386 274 192 595 312 273 391 709 262 522 76 217 346 110 98 507 878 445 533 189 110 483 999 98 434 820 162 194 4 91 254 836 106 296 314 226 281 485 …
Output: 2616

Constraints:

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

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