CT59458

Mason's Lunar bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

It is audit day at the orchid house of Bloomglass. Mason spreads the bridges records across the table and picks up a sharp pencil. 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 <= 1309; 0 <= m <= 3927; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 569 568 1 569 1 379 68680 27 196 287200 12 284 275198 88 309 571433 423 560 758627 190 508 993227 315 378 68521 26 219 472549 85 252 949357 67 193 662907 283 481 365822 210 544 712059 125 333 866080 369 455 156558 93 548 288727 50 160 984785 314 404 226218 203 374 870559 106 407 401101 6 19 896313 24 367 417423 74 98 937817 111 411 540979 490 544 196107 372 384 631965 400 483 108484 142 568 978764 85 179 720184 395 472 458303 356 535 263747 291 320 38324 301 323 720587 47 195 645213 62 470 671821 298 337 453366 162 436 708669 8 293 236858 141 302 955243 122 325 26945 303 509 13566 114 358 468174 68 499 718195 44 53 732541 186 353 93029 30 374 5570 26 255 462772 299 330 892811 339 480 403791 375 476 786707 194 353 531951 105 201 819612 217 334 369437 153 259 775928 357 369 664769 184 365 50…
Output: 3641866

Example 2:

Input: 672 2399 1 672 163 400 19348 349 589 333118 410 566 47870 289 449 981201 116 548 900152 465 491 231194 513 641 726181 416 577 749887 435 626 37496 52 61 398825 30 382 690608 111 571 192691 164 281 35570 496 616 628060 111 651 53491 107 200 246653 151 591 20030 83 225 839514 203 244 403586 213 475 417553 105 207 81025 48 554 407582 4 359 315895 196 250 216619 188 589 57172 44 205 510870 110 273 909881 114 255 141900 71 273 629285 223 262 954445 338 600 225507 83 87 39340 108 213 115809 9 403 607391 36 139 307366 286 465 577852 203 532 523309 138 594 770965 101 431 79212 289 602 560524 13 656 739495 210 417 376321 78 463 148588 505 657 76208 70 496 432643 47 356 29892 624 656 956989 203 625 452220 145 481 679084 22 427 555673 151 393 834160 446 586 518624 405 417 153154 64 549 338369 61 329 …
Output: 853513

Example 3:

Input: 598 3230 1 598 249 392 98899 48 193 889776 541 593 761201 294 492 962888 441 535 339888 436 449 800575 16 507 176183 178 356 647667 272 546 501434 509 594 404371 168 242 863108 274 564 231363 305 507 499978 317 550 328586 32 504 276127 94 120 919636 61 473 729198 58 375 773746 228 311 867660 162 580 597717 130 543 210310 54 541 501540 90 134 75923 115 146 361582 250 492 206304 126 550 535403 30 116 199043 288 487 860117 127 501 634854 288 347 96765 284 397 219085 60 466 356260 298 541 434617 9 540 422807 87 567 596143 320 338 211625 348 404 778678 321 555 440529 26 385 619170 429 504 528605 105 310 685769 112 273 70379 215 505 578508 181 232 485331 67 561 940840 320 393 533705 229 560 126068 20 358 886959 432 511 576788 125 265 987512 295 378 638193 34 134 199088 472 551 533044 373 431 592…
Output: 752309

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Mason's Lunar bridges - MEDIUM Coding Problem | CodeTikki