도로포장
https://www.acmicpc.net/problem/1162
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 12239 | 2532 | 1530 | 21.106% |
문제
준영이는 매일 서울에서 포천까지 출퇴근을 한다.
하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다.
돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다.
문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때
최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다.
도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다.
또한 편의상 서울은 1번 도시, 포천은 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.
입력
첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과
포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다.
M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다.
도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.
출력
첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.
예제 입력 1
4 4 1 1 2 10 2 4 10 1 3 1 3 4 100
예제 출력 1
1
추가 예제
https://codeforces.com/blog/entry/95032
예제 입력 A
4 6 1 4 3 3 3 1 3 2 1 3 2 4 200 3 2 300 1 2 200
예제 출력 A
3
예제 입력 B
10 20 3 1 3 50 1 8 3 1 10 15 2 10 37 2 9 42 2 9 14 2 3 44 2 8 26 3 6 80 3 6 60 3 7 12 3 9 66 3 4 81 4 8 6 5 10 45 5 6 73 6 7 83 6 7 83 7 10 14 8 10 59
예제 출력 B
0
예제 입력 C
100 500 3 1 9 574 1 11 907 1 18 924 1 14 652 1 21 900 1 14 456 1 12 997 2 10 174 2 15 872 2 22 658 2 13 621 2 10 72 2 13 198 2 15 153 2 21 922 2 7 749 2 21 469 2 18 154 2 12 13 3 12 667 3 9 560 3 4 949 3 22 829 3 14 758 4 23 952 4 21 126 4 18 498 4 22 299 4 20 552 5 17 431 5 14 978 5 24 749 5 24 135 5 8 485 5 13 87 5 17 51 6 13 201 6 23 223 6 12 791 6 9 424 6 26 998 6 24 186 6 14 658 7 8 786 7 18 410 7 16 615 8 9 952 8 21 44 8 17 404 9 12 555 9 10 433 9 17 476 9 13 39 9 28 54 10 18 803 10 25 909 10 29 108 10 28 157 10 25 615 10 29 526 11 22 942 11 25 688 11 16 372 11 21 73 11 18 172 12 14 813 12 18 18 12 28 717 12 14 890 12 31 707 12 29 769 12 24 53 12 24 977 13 24 312 13 29 96 13 23 150 14 31 146 14 17 195 14 28 750 14 28 381 14 16 167 14 33 426 15 22 564 15 32 495 15 27 938 15 20 6 15 29 273 15 18 407 15 28 364 15 24 786 16 17 277 16 28 931 16 35 320 16 17 471 17 20 510 17 18 687 17 35 949 17 34 427 17 27 238 18 20 633 18 25 432 18 31 494 19 29 651 19 21 859 19 20 399 19 39 436 19 34 550 20 33 13 20 24 127 21 31 341 21 22 828 21 23 120 21 34 911 22 23 264 22 33 888 22 35 132 23 38 914 23 42 43 23 33 151 23 36 474 23 24 273 23 29 373 23 34 755 24 32 483 24 30 599 24 34 421 25 35 329 25 28 680 25 37 579 25 42 480 26 43 882 26 45 399 26 27 833 26 45 15 26 38 773 26 38 724 27 43 242 27 33 270 27 37 252 27 29 69 28 33 295 28 36 350 28 44 619 28 42 542 28 34 242 28 33 876 28 31 500 28 46 715 28 43 934 29 41 559 29 32 430 29 34 721 29 39 466 30 37 822 30 39 777 30 36 373 30 47 145 30 33 256 30 36 219 31 50 986 31 50 557 31 38 275 31 40 6 31 42 536 31 49 791 31 36 86 31 43 552 32 49 447 32 34 865 32 39 982 32 37 818 33 47 168 33 48 140 33 45 365 33 51 402 33 45 5 33 49 314 34 35 758 34 44 113 34 42 421 34 35 350 34 47 330 35 54 253 36 47 601 36 37 727 36 40 958 36 51 847 36 44 105 36 38 641 36 46 850 37 42 886 37 38 695 37 41 299 37 55 196 37 51 747 37 49 874 38 52 849 38 57 443 38 50 91 38 55 213 38 44 708 38 49 285 38 55 17 39 46 6 39 50 70 39 58 450 39 53 609 40 41 791 40 47 199 40 57 718 40 42 821 40 59 40 41 56 666 41 53 978 41 60 380 41 56 491 42 51 992 42 62 452 42 44 694 42 60 567 42 60 452 42 43 922 43 53 721 43 51 974 43 45 765 43 62 779 43 54 392 44 49 935 44 63 704 45 53 903 45 55 343 45 50 285 46 56 899 46 60 810 46 65 464 46 61 661 46 66 107 47 50 285 47 59 288 47 59 28 47 66 351 47 55 20 47 67 802 48 52 750 48 62 235 48 53 281 48 55 187 48 62 848 48 52 278 48 68 896 48 52 357 49 67 800 49 66 491 49 51 577 49 65 661 50 55 912 50 63 372 50 54 177 50 57 77 50 57 318 50 66 363 50 56 665 51 56 106 51 66 847 51 69 879 52 53 573 52 61 391 52 67 135 52 58 125 52 69 630 52 53 104 53 60 226 53 70 844 53 58 473 53 57 687 53 72 111 53 57 791 54 72 630 54 70 203 54 63 47 55 60 751 55 75 194 55 56 28 55 70 459 55 69 127 55 61 302 55 60 97 55 66 443 55 61 847 56 61 925 56 62 90 57 77 776 57 65 289 57 74 545 58 64 334 58 59 163 58 77 775 58 66 671 58 66 182 59 70 971 59 64 915 59 73 702 59 60 336 59 68 747 59 66 829 60 75 804 60 64 421 60 75 65 60 67 224 60 75 802 60 62 803 61 78 545 61 66 429 61 70 171 62 79 748 62 78 280 62 67 39 62 68 968 62 79 733 63 82 657 63 70 70 63 78 175 64 79 568 64 66 675 64 77 29 64 74 280 64 81 362 65 73 417 65 74 795 65 71 886 65 75 70 65 66 633 66 77 117 66 77 28 66 71 648 66 72 102 66 84 914 66 84 358 66 70 98 66 67 406 66 86 734 67 70 651 67 82 747 67 79 180 67 69 248 67 81 34 67 71 707 67 83 687 67 79 828 68 69 66 68 77 425 69 72 721 69 83 305 69 71 464 69 71 565 69 72 1 70 75 740 70 87 148 70 82 374 70 85 642 70 89 300 70 86 84 70 75 437 70 83 738 71 84 220 71 80 520 71 82 856 71 90 955 71 82 788 71 88 861 71 83 432 71 80 309 71 75 207 72 75 723 72 92 412 72 87 714 72 77 222 72 92 303 73 76 483 73 93 721 73 74 940 73 90 929 74 86 181 74 78 956 74 91 433 74 88 942 74 87 451 74 75 354 74 85 968 74 79 887 74 88 475 74 83 485 74 89 728 75 80 745 75 78 517 75 95 212 75 76 166 75 78 243 75 79 857 75 84 283 76 95 985 76 81 891 76 83 518 76 79 335 76 90 381 76 89 409 76 88 92 76 87 218 77 90 289 78 81 954 78 93 732 78 94 733 78 94 209 79 90 47 79 92 322 79 90 832 79 94 949 79 98 147 79 92 282 79 99 20 80 96 176 80 99 312 80 84 80 80 94 514 80 93 209 80 89 267 81 94 694 81 93 673 81 97 445 81 85 108 82 83 698 82 100 213 82 84 963 82 91 175 82 94 69 82 89 890 82 86 375 82 92 949 83 100 397 83 100 685 83 99 696 83 96 276 83 97 260 83 99 299 83 85 850 83 96 522 83 96 855 84 85 903 84 85 733 84 87 230 84 92 192 84 97 833 84 95 372 85 100 392 85 91 525 85 89 378 85 86 718 86 94 132 86 88 966 87 91 49 87 90 464 87 88 411 87 92 811 87 91 25 88 94 794 88 97 57 88 89 412 88 95 72 88 95 389 88 89 504 89 100 86 89 94 953 89 91 612 90 92 476 90 93 29 90 99 771 90 95 928 90 93 381 91 99 868 91 98 872 91 95 281 91 96 960 92 98 703 92 98 776 92 95 252 92 95 942 93 95 994 93 99 107 94 97 80 94 96 971 94 99 183 95 97 186 95 97 480 96 97 64 96 98 476 96 100 847 96 100 164 97 100 266 98 100 258 98 100 520
예제 출력 C
278
예제 입력 D
500 2000 10 1 2 47274 1 12 37961 1 13 94095 1 5 88061 1 4 72314 1 18 87558 1 20 5639 1 3 30386 2 21 33567 2 15 39436 2 10 44870 2 19 69504 2 4 56250 2 20 22719 2 13 93754 2 8 56582 3 19 13558 3 14 50762 3 6 77110 3 11 21558 3 8 64302 3 15 12473 3 23 18576 3 21 6410 3 15 7202 3 14 18589 3 4 68753 3 8 13354 3 7 72886 4 21 94588 4 18 72136 4 16 17383 4 13 84674 4 20 61758 4 5 83447 4 7 12660 4 14 58771 4 13 68305 4 7 91684 5 16 50471 5 19 24937 5 19 23702 5 7 20186 5 10 28285 5 10 70408 6 13 1201 6 19 91637 6 24 74195 6 11 64295 6 8 68237 7 21 53561 7 26 68637 7 11 13091 7 18 94358 7 21 58748 7 27 34259 8 24 51565 9 17 33661 9 13 38935 9 23 1359 9 11 29224 10 28 52615 10 24 26202 11 27 57648 11 26 21100 11 30 37919 11 25 36533 11 16 64650 12 29 30710 12 26 69743 12 19 24943 12 22 85652 13 26 5189 13 22 76091 14 18 74467 14 29 73065 14 23 40286 14 28 18694 14 17 55006 15 20 56263 15 28 52617 15 35 32795 16 22 26674 16 27 65443 16 19 2850 16 19 76774 17 34 52374 17 29 73811 17 32 9994 17 22 71816 18 29 33171 18 22 37938 18 30 70627 18 19 99734 18 36 58617 18 35 33680 19 27 54151 19 28 19130 19 24 2456 19 39 13648 19 32 82353 19 24 54801 19 39 18375 20 31 31320 20 21 70706 20 27 24235 20 39 2833 21 31 93940 21 28 47822 21 35 25839 21 41 40067 21 41 8659 22 34 29853 22 33 90852 22 37 99279 23 36 49784 23 40 14298 23 43 9145 23 37 16140 24 34 60347 25 37 57063 25 42 44414 25 26 96468 25 31 98613 25 28 92759 26 43 80312 26 35 53781 26 35 56776 26 45 46115 27 38 94465 27 35 29472 27 41 81188 27 43 19846 28 30 68326 28 46 16861 28 36 30947 28 40 53185 28 39 90455 28 33 98485 29 41 27390 29 38 94103 29 40 85194 29 46 96646 29 46 82566 30 40 946 30 48 49673 30 45 92290 30 33 65852 30 33 93468 30 41 93439 31 50 87585 31 36 81065 31 34 95430 31 42 59199 31 32 55754 31 32 28055 32 42 22133 32 48 16798 32 48 89710 32 34 29078 32 46 60128 33 49 62147 33 50 59454 34 43 26888 34 35 40180 34 36 43246 34 36 3360 34 46 62693 34 38 89008 34 43 70686 34 51 13774 35 38 46280 36 50 99369 36 38 17401 36 39 70950 36 39 78320 36 54 97223 36 40 50137 37 55 21307 37 50 59760 37 51 5543 37 40 83545 37 38 60626 37 44 94015 38 57 44135 38 55 84764 38 50 46038 38 53 67321 38 48 7180 39 44 10790 39 43 18037 39 42 99116 39 57 70175 39 48 64017 39 56 90657 40 60 62284 40 53 63963 40 48 68873 40 55 65520 40 53 92799 40 50 32641 41 44 84480 41 52 17436 41 45 57089 41 47 1941 42 60 12251 42 47 42803 43 53 98178 43 54 43631 43 54 62276 43 50 94472 44 53 52931 44 56 52090 44 46 2502 45 64 48336 45 52 79165 45 65 8600 45 64 31620 45 62 27015 46 65 51082 46 66 41644 46 62 13042 46 57 89545 46 58 61801 46 48 69391 47 61 45529 47 51 94953 47 60 39758 48 52 48188 48 62 30904 48 52 76301 48 57 71120 48 64 94931 48 61 55006 49 67 6287 49 50 2682 49 57 99290 49 58 95921 49 64 61182 49 55 96938 49 69 21495 50 57 6970 50 60 40155 51 62 75941 52 58 55528 52 63 35894 52 61 89100 52 66 9025 53 66 85099 53 64 71127 53 59 80925 53 63 84858 53 54 41190 53 55 82385 53 56 85866 53 70 32893 54 72 20064 54 71 45757 54 64 20598 54 69 12544 55 60 66230 55 69 61418 55 61 97815 56 67 93896 56 60 43111 57 77 71815 57 58 89064 57 76 26769 57 70 59736 58 75 25434 58 74 23141 58 59 34090 59 64 85761 59 70 67020 59 73 26499 59 60 85750 59 65 57422 59 73 13994 59 76 85989 59 60 63565 59 63 49055 60 78 51029 60 66 17464 60 64 48857 61 78 32328 61 70 6803 61 81 85016 61 72 90073 62 79 92562 62 76 70157 62 73 59465 62 66 1329 62 72 65081 64 66 43343 64 83 98559 64 81 46520 64 77 796 65 66 28075 65 69 45350 66 82 62216 66 72 10751 66 73 16965 66 86 87658 66 85 89970 66 82 34988 67 71 43304 67 79 86336 68 79 92935 68 69 12958 68 74 20688 68 71 32924 68 77 83600 69 83 52276 69 76 32687 70 82 61640 70 82 45831 70 88 93492 70 84 15129 71 73 81396 71 72 66332 71 91 50870 72 74 63335 72 91 42576 73 91 79345 73 82 78117 73 87 38759 73 91 30644 73 75 27998 74 85 32449 74 91 16106 74 84 23881 74 93 48270 74 86 60656 74 83 74773 75 80 21789 75 78 71296 75 91 74120 76 83 85856 76 90 83346 76 93 81687 76 80 68166 76 90 63482 76 79 90207 76 90 30794 76 94 1883 77 81 1076 77 96 47614 77 88 53221 78 93 98426 78 84 95345 78 83 73021 79 82 2118 79 86 66427 79 92 87981 79 85 6269 80 82 88977 80 96 59562 80 81 70595 81 95 19798 81 91 55420 82 100 81689 82 96 89076 82 91 84241 82 100 35027 83 99 32458 83 97 47799 83 99 64508 83 85 88406 83 90 97254 83 103 85556 84 94 80362 84 87 52582 84 91 41001 85 93 13496 85 96 41760 86 94 93196 86 103 25219 86 91 60324 87 107 3161 87 103 82082 87 100 80024 88 97 69053 88 102 84291 88 104 80423 88 92 70449 88 107 65934 89 107 51568 89 91 61759 89 93 22793 89 109 68161 90 103 65366 90 101 50561 91 98 209 91 101 9306 92 94 95167 92 102 58968 92 93 21709 92 100 30301 93 112 72873 93 99 38019 93 99 39332 93 96 42434 93 101 51063 93 99 2580 94 101 13028 95 101 71000 95 97 65118 95 108 70773 95 103 92172 95 109 90943 95 110 37977 96 113 64318 96 98 336 96 102 61469 96 114 454 96 115 68928 96 109 16072 96 116 22650 96 102 93111 97 116 7309 97 117 57569 98 110 42691 98 112 1378 98 99 73278 98 105 94395 98 117 27195 98 108 86241 98 107 60188 99 106 13113 99 106 41221 99 103 85859 100 110 40471 100 101 26148 100 108 37372 100 114 22745 100 115 92258 100 119 93897 101 116 87116 101 111 6970 101 114 41573 101 120 1782 102 115 48758 102 121 44303 102 107 10985 102 104 22257 103 115 36959 103 121 3143 103 108 33392 104 122 12817 104 110 17201 105 108 26388 105 125 74395 105 123 24498 106 113 57961 107 108 91644 107 115 22577 107 121 31478 108 112 42295 108 110 60666 108 127 50703 108 109 20527 109 110 44818 109 116 93290 109 122 95250 109 118 68182 109 121 63169 109 114 64624 110 115 45807 110 112 7942 110 129 89347 111 129 24850 111 118 40028 112 116 19474 112 120 91512 112 127 49066 112 121 1220 113 121 52299 113 118 37973 113 122 5909 113 122 28727 113 127 96587 114 124 67812 114 129 30502 114 124 28167 114 123 573 114 129 72433 115 123 195 115 119 81084 115 125 9538 117 120 3311 117 118 6327 117 135 95073 117 121 11421 117 129 30033 117 126 8607 117 121 47157 117 126 21224 117 137 7937 117 131 33997 117 119 13803 118 138 74814 118 121 71581 118 119 25448 118 129 76954 118 129 1518 118 122 56101 118 126 90042 119 129 61614 119 122 23358 119 138 38878 119 139 20384 119 138 53461 119 127 18598 119 135 46322 120 124 39245 120 123 14627 120 126 46401 120 136 42653 121 122 3608 121 138 5038 121 140 95807 121 139 39793 122 123 3658 122 135 68083 122 133 24118 123 142 81124 123 133 77169 123 136 98447 123 126 85756 123 132 34477 124 143 70079 124 142 438 124 144 61614 125 140 58554 125 144 26299 125 143 26784 125 135 66108 126 140 17501 126 137 81391 126 133 11303 126 133 87483 127 143 84890 127 133 31816 127 145 22507 127 140 27522 128 144 55419 128 134 51722 128 133 8926 128 135 61742 128 137 29852 128 146 50378 128 148 47064 128 129 83902 129 133 72143 130 139 37777 130 135 24292 130 150 56087 130 150 64266 131 146 89648 131 146 96688 131 143 67569 131 132 33668 132 148 67398 132 141 71825 133 145 25224 133 135 66923 133 152 54091 134 149 97565 134 151 29516 135 145 37073 135 151 20889 136 137 24112 136 151 97569 136 152 7610 136 144 57374 137 146 31624 137 144 47344 137 151 69711 137 142 76188 138 150 14296 138 151 79972 138 140 50575 138 149 85385 138 149 13400 138 144 71054 139 148 59913 139 158 84655 139 141 55716 139 154 75649 139 150 89251 139 156 88636 139 151 8601 140 156 24375 140 150 25542 140 144 2403 140 146 16619 140 145 49978 141 153 91423 141 142 76361 142 158 96497 142 158 97164 142 161 99792 142 158 42697 143 150 39175 143 155 37360 145 153 15020 145 163 22305 145 165 68492 145 163 13967 145 147 1887 145 165 94515 146 150 1426 146 157 65315 146 159 70516 146 148 1589 146 147 79440 146 163 65343 147 156 61805 147 167 1105 147 149 39683 147 163 10277 147 161 29487 147 149 20341 147 153 47288 147 162 27502 148 162 30979 148 152 17924 148 157 30932 148 158 21063 148 158 85942 149 152 17028 149 154 64397 149 151 98094 149 162 82554 149 150 80126 149 156 87550 149 162 75289 150 153 85955 150 154 88241 150 164 28871 150 163 14143 150 153 13786 150 153 94959 150 169 50778 151 164 81148 151 161 1757 151 153 71102 151 170 81424 151 165 26769 151 166 94605 152 167 1401 152 162 58209 152 161 93826 152 162 1999 153 162 77356 153 169 86703 154 170 69127 154 161 80012 154 156 7643 154 168 26189 154 160 74508 155 175 47985 155 173 19164 155 156 2928 155 161 67729 155 169 87567 155 158 69032 156 158 26676 156 162 70634 156 174 1164 156 167 48735 156 170 84906 157 176 68240 157 160 864 159 160 19393 159 172 274 159 170 61694 159 178 14457 159 174 75189 159 173 59206 160 178 53413 160 166 54248 160 163 99589 160 175 8623 161 177 28233 161 170 62962 161 167 352 162 174 89950 162 175 90577 162 172 96287 162 180 18855 163 182 5732 164 176 71035 164 172 1438 164 165 71153 164 171 62906 164 180 2341 164 169 21728 165 174 35496 165 168 82074 165 177 10757 166 170 46712 166 176 22649 166 177 27891 166 185 18547 166 180 14962 166 181 56072 166 183 63146 167 170 5865 167 182 23464 167 179 70425 167 172 91796 167 182 15274 167 177 286 167 180 4408 168 188 67404 168 169 37352 168 176 42168 169 175 74689 169 183 80979 169 172 82332 169 179 7070 169 177 20777 170 187 20987 170 171 83907 170 186 53807 171 178 78836 171 175 71531 171 185 4587 171 172 57243 171 189 18141 171 190 8415 171 189 70473 171 186 90584 172 192 50769 172 174 12741 172 185 45430 172 177 51534 172 184 49636 173 176 80 173 182 75118 174 191 91707 174 187 8074 174 180 54584 174 183 3200 174 192 55888 174 179 48207 174 177 80185 175 187 25889 176 188 90257 176 186 43808 176 193 20128 176 194 47417 176 191 26009 176 189 50704 176 191 38065 177 182 11076 177 178 86212 177 195 40596 178 193 46852 178 189 99042 178 181 71011 178 184 7511 179 190 33987 179 192 29911 179 198 87147 179 195 54726 180 197 95213 180 183 15644 180 196 19654 180 192 82805 181 189 61542 182 194 45596 182 192 71265 182 191 27481 182 188 51045 182 191 21656 182 186 43372 182 201 94188 182 188 80676 182 202 62163 183 195 27022 183 185 70300 183 186 56884 185 203 83543 185 189 20366 185 204 67852 185 199 21159 185 199 21342 185 188 76155 186 202 92273 186 197 63299 186 193 58362 186 195 45237 186 188 70534 187 191 8998 187 190 18350 187 207 51617 187 204 12537 187 203 70221 187 192 25090 188 195 97545 188 202 40219 189 200 92683 189 196 41523 189 198 87834 189 204 87140 189 190 86568 189 201 14256 189 197 83140 190 193 70237 190 195 84511 190 198 39182 191 206 58638 191 195 87605 191 211 91583 191 197 92038 191 198 6559 191 199 6749 191 198 65307 191 195 62658 192 211 47526 192 193 52251 192 199 21690 192 195 18819 192 196 66819 192 194 89450 193 209 96200 193 195 28686 193 205 12827 193 207 78600 194 197 53523 194 207 67753 194 200 24280 194 210 30135 194 199 85039 194 199 36275 194 205 37958 194 205 56397 195 211 34627 195 196 88234 195 204 7512 195 204 54021 195 202 22633 196 204 99731 196 213 62129 196 199 15547 196 202 946 196 216 40614 197 213 11851 197 204 3843 197 211 93007 197 204 88287 197 203 30596 198 212 43603 198 213 36457 198 210 35838 198 204 731 199 200 73956 199 200 50266 199 214 199 199 210 68760 199 209 28165 200 201 15569 200 202 82306 200 220 8081 200 203 47192 200 207 28227 200 216 19612 200 211 40102 200 204 26515 201 215 10613 201 220 94437 201 212 62422 201 210 33425 201 220 40674 202 217 26817 202 213 3671 202 204 43103 202 205 32539 203 213 55063 203 223 27122 203 212 81967 203 204 22066 203 212 48949 203 219 70949 204 223 40248 204 218 38414 204 218 48457 204 212 65568 204 213 1827 204 219 95019 205 217 98553 205 220 63784 205 211 18399 205 217 59351 206 215 59964 206 211 58022 207 219 34111 207 221 91013 207 223 89375 207 225 13577 207 226 54071 208 218 10766 208 226 60098 209 223 44656 209 221 14419 209 213 85115 209 219 95992 210 230 30289 210 214 47327 210 212 45852 211 221 33098 211 218 12405 211 212 52032 211 224 56677 211 212 93444 211 229 74393 211 213 89722 212 217 11995 212 216 22102 212 217 54607 212 224 1687 212 222 22363 213 227 87493 213 217 347 213 218 27319 214 228 69779 214 218 76632 214 224 32326 214 233 68298 214 216 45783 214 218 52555 214 221 94079 214 215 70328 214 232 20478 214 226 23295 215 229 50149 215 224 83817 215 217 46051 215 235 77496 215 224 45390 215 222 47197 216 217 61220 216 235 76046 216 236 21347 217 223 69638 217 230 70182 217 229 64189 217 234 49281 218 224 48713 218 231 85247 218 230 13045 218 227 56441 219 220 79617 219 228 90586 219 234 95450 219 236 60049 220 231 33787 220 233 75383 220 232 21828 220 233 37298 220 240 42475 220 229 91305 220 237 68065 220 235 30920 221 241 34630 221 222 33222 221 235 34030 221 230 65685 221 227 30357 221 234 52730 222 223 59650 222 230 88766 222 227 22537 223 239 52596 224 234 26083 224 236 41212 225 229 75697 225 240 4007 226 227 52751 226 239 33116 226 230 54758 226 237 78138 227 231 69476 227 243 88815 227 230 17008 227 245 14361 228 230 96168 228 243 73643 228 246 61357 228 232 21074 228 241 65922 230 244 11161 230 236 64049 231 246 52729 231 239 4591 232 239 47029 232 233 65473 232 247 71621 232 240 75918 233 235 42736 233 242 29159 233 239 65248 233 242 17157 233 249 73825 233 253 19553 234 239 15851 234 235 67306 235 237 98416 235 252 90274 235 247 1495 236 244 71546 236 247 9786 236 244 74543 236 256 93181 237 246 77669 238 244 63088 238 249 68868 238 248 74743 238 239 15311 239 247 59960 239 250 18892 241 260 92613 241 258 8433 241 251 85754 242 247 48508 242 246 23289 242 262 31047 242 247 77252 243 260 34969 243 258 64683 243 252 656 243 254 42551 243 252 30653 244 255 90086 245 255 36641 246 255 3128 246 252 95303 247 262 2169 248 255 11889 248 262 57456 248 253 89816 248 260 99607 249 250 62142 250 262 6796 250 265 8375 250 252 33111 250 257 3047 250 262 47005 251 254 44893 251 264 63636 251 268 82160 252 253 41448 252 261 94409 252 261 77678 252 259 12498 252 270 23768 252 259 84957 252 260 58136 252 261 11656 252 267 94520 253 261 68847 253 260 25032 253 254 81858 254 264 26601 254 272 47193 254 265 70107 254 268 27270 254 260 14546 255 265 48762 255 272 77422 255 261 51162 255 262 1978 256 274 64387 256 272 36149 257 276 19724 257 269 38032 258 264 74635 258 276 50440 258 277 54650 258 272 74692 258 263 70091 259 266 32097 259 272 72378 260 275 18012 260 269 25074 261 266 92031 261 268 52099 261 276 2576 261 263 77187 261 272 48806 261 276 39794 261 271 910 261 275 9218 261 262 31677 261 263 86758 262 277 48902 262 269 27514 262 265 21791 262 273 85669 262 282 63407 263 279 82522 263 269 22794 264 281 42837 264 281 52017 264 276 67668 265 275 88083 265 281 43091 265 276 8232 265 283 29164 265 283 37904 265 279 55135 266 277 98359 266 271 78623 266 284 52028 266 276 46941 266 284 9331 266 281 38905 267 268 50583 267 275 75910 267 276 59332 267 272 24302 267 284 72148 267 276 52454 267 274 89351 268 272 41810 268 269 81705 268 285 38972 268 277 98159 268 283 31201 269 271 38002 269 283 83772 270 286 67583 270 272 37256 270 286 4158 271 272 2704 271 288 41218 271 284 32489 271 291 95984 271 278 70195 272 291 34051 272 289 13115 272 275 48016 273 293 43541 273 276 54901 273 282 98264 273 277 64487 273 280 97050 274 289 67005 274 282 54766 274 280 81863 274 284 67914 275 283 11411 275 284 61790 275 292 12464 276 290 80242 276 289 69156 276 296 81504 276 290 16892 277 291 10194 277 293 33923 277 286 66988 277 294 72452 277 281 75437 277 294 52403 277 283 25555 278 284 2697 278 297 91245 278 296 19614 278 282 89764 278 291 4045 278 298 64300 278 283 70226 278 296 79559 278 285 50742 279 294 85292 279 293 19295 280 289 45942 280 290 74145 280 289 36447 280 293 51786 281 298 33439 281 285 30781 281 293 11248 281 294 51501 282 288 7060 282 290 26604 282 287 30152 282 296 48788 282 296 74026 284 285 77094 284 286 64042 284 292 76594 284 285 51693 285 305 88006 285 292 95368 285 288 45738 285 292 63627 285 303 94283 286 300 67019 286 306 85318 286 298 42324 286 295 12840 286 288 46127 287 300 17876 287 302 6881 287 304 81364 287 301 2196 287 296 92899 287 301 89434 287 294 62059 288 307 90798 288 304 92507 288 293 46558 289 309 10331 290 295 85430 290 298 4210 290 307 85598 291 305 76104 291 309 88328 291 304 44792 291 309 11490 291 303 81320 292 310 515 292 297 91260 292 308 26819 293 304 33911 293 296 14651 294 299 70148 294 305 34064 294 298 42869 294 303 62202 294 310 58361 294 298 76618 295 303 72099 295 314 1707 295 300 20041 295 315 18151 296 311 59850 296 306 11373 296 309 93459 296 315 92898 296 311 87364 296 316 89383 296 306 77150 296 308 4905 297 314 20960 297 307 10830 297 312 19459 297 303 99278 298 318 86114 299 306 88992 300 315 15630 300 302 99624 300 315 92193 300 306 17693 300 314 58321 301 308 49183 302 320 10264 302 306 30760 303 310 86273 303 310 90306 303 305 61557 303 318 50890 303 320 85160 303 315 19940 304 310 14093 304 312 16224 304 314 75073 304 308 20059 305 315 41478 305 315 27400 306 318 45102 306 311 31344 307 316 41116 307 326 25096 307 322 94549 307 326 80115 307 314 71196 307 323 29735 307 320 31855 307 314 36356 308 316 69868 308 315 35522 308 315 20616 308 312 90538 308 312 85953 308 315 90040 308 327 50098 309 318 97519 309 323 93543 310 318 12014 310 319 39442 310 319 12178 310 330 31533 310 321 28028 311 330 80209 311 316 35972 313 324 81319 313 314 91246 314 328 43244 314 329 67372 314 315 16218 314 332 92932 314 318 42805 314 333 24468 315 321 20755 315 318 14451 315 322 62688 315 332 62969 316 335 37648 316 329 99746 316 329 59622 316 333 78702 317 337 62517 318 324 32141 318 325 42677 318 319 2730 318 322 7993 318 333 66709 319 339 36990 319 324 91413 319 326 23846 319 331 85886 320 323 67526 321 337 78655 321 323 81437 322 342 32175 323 326 12694 323 335 20314 324 330 54351 324 340 61958 324 339 5675 324 343 76779 324 331 49349 325 345 99778 325 332 7926 325 326 47276 325 336 31801 326 333 10343 326 331 53165 326 345 42333 326 335 57147 326 331 23149 326 342 96296 326 344 81806 327 343 52829 327 329 97761 328 345 76662 328 338 8311 328 339 91783 329 335 26627 329 341 24085 329 343 12368 329 342 83188 329 342 80694 330 336 50317 330 345 76793 330 334 89683 330 341 81043 330 338 11574 331 336 13876 331 336 94615 331 347 87159 331 338 99869 332 337 25814 332 346 88071 332 351 55056 332 339 98211 332 346 23930 333 342 91695 333 343 17588 334 344 41198 334 343 18990 334 350 6301 335 344 70314 335 347 25638 335 345 23075 336 347 93189 336 347 11071 337 341 72729 337 342 70241 337 344 19949 337 352 26178 337 339 1784 338 348 4433 338 353 98897 338 354 39448 338 352 93991 339 353 22801 339 344 62145 340 347 83193 340 350 38801 340 347 76724 340 354 52686 340 356 39265 340 342 69714 341 342 33935 342 354 3201 342 343 86112 342 348 77787 342 361 64973 342 348 65956 343 350 30778 343 344 61154 343 357 44572 344 364 29174 344 363 67992 344 358 21183 344 363 77997 344 356 42363 345 363 981 345 357 35728 346 356 26168 346 366 21498 346 359 69826 346 363 82406 347 359 96342 347 357 57454 347 360 84931 347 353 68341 347 366 59270 347 363 42774 348 349 73568 348 354 88872 348 353 45305 348 352 98293 348 363 19844 349 355 52715 349 356 75909 349 365 66402 350 355 90065 350 370 21631 350 369 91797 350 360 62024 352 363 57498 352 367 5481 352 360 77095 352 372 87911 352 353 12087 352 359 16691 353 358 38445 353 368 32737 353 369 54485 354 368 88586 355 361 99053 355 362 49055 355 368 18420 355 364 71887 356 374 83217 356 365 21722 356 366 87383 356 370 44006 356 371 72408 357 374 74674 357 365 43496 357 374 75434 357 364 69683 357 373 69242 357 368 84081 357 374 19990 358 377 15656 358 361 51258 358 367 71491 359 372 31101 359 371 44947 360 377 90955 360 364 82339 361 375 91316 361 368 93728 361 367 71039 362 363 9352 362 380 55699 362 373 12674 362 369 70311 362 371 19423 362 364 70615 362 364 1007 364 379 1626 364 370 11959 364 383 84243 364 367 25489 365 369 40949 365 381 47893 365 381 10778 366 373 9271 366 370 91797 367 383 30689 367 383 88519 367 375 43538 367 370 82495 367 368 3543 368 371 11813 368 379 56249 368 378 39433 368 380 30279 368 375 56711 369 378 75813 369 379 21886 369 389 10117 369 371 8337 369 371 46950 369 379 40702 370 386 50154 370 377 49197 370 378 22556 370 386 30235 370 388 55553 371 380 97512 371 375 50526 371 391 56301 371 377 48523 371 373 78178 371 380 11047 372 379 85231 372 379 61164 372 389 84834 373 386 58836 373 385 70016 373 379 939 373 391 99007 373 378 39703 374 386 5859 374 390 77878 374 377 49303 375 383 51607 375 382 91743 375 377 88236 376 387 37052 376 385 67709 376 387 5872 376 388 13729 376 393 80914 376 380 43929 376 378 45428 377 383 76781 377 384 93491 377 393 16347 379 393 21279 379 386 26253 379 397 38588 379 389 59723 379 395 14855 380 394 55344 380 385 20477 380 399 80321 381 384 58281 381 396 61052 381 398 3196 382 384 30925 382 393 47746 382 397 11959 382 393 46930 382 401 9089 383 400 76295 383 394 41422 383 397 22733 383 395 9266 383 385 32621 384 396 20786 384 388 79869 385 391 42027 385 401 7585 385 403 89685 385 393 9799 386 399 42681 386 406 90130 386 395 79601 386 397 19572 386 391 75920 386 405 55826 386 394 35746 387 394 62307 387 407 11556 387 402 99913 387 398 26039 387 399 19843 388 405 15665 388 396 45730 388 407 9493 389 391 42042 389 400 71748 389 401 43627 389 403 5076 390 399 73169 390 406 94528 391 403 47145 391 403 86592 391 406 20454 391 410 93146 391 398 55650 391 401 61433 392 407 79288 392 406 73773 392 409 98082 392 404 60883 393 406 8286 393 409 84839 393 397 46103 393 402 65367 393 399 3745 394 414 9530 394 400 32644 394 413 10176 394 398 17981 395 402 93675 395 411 94945 395 403 5071 395 413 3060 395 396 5814 395 405 74058 396 411 10344 396 397 35627 396 415 1129 396 407 78844 397 416 75234 397 400 90523 397 412 22468 397 416 9835 397 405 14955 398 410 32738 398 401 73552 399 407 72495 400 411 91137 400 416 287 400 403 12645 400 417 59265 400 402 99370 401 421 69897 401 402 88418 401 410 22723 402 411 59982 402 416 84233 402 412 9049 402 409 61350 403 406 61000 403 410 8539 403 411 11808 403 405 65345 403 423 56056 404 414 73297 404 418 20353 405 420 53361 405 416 95540 406 420 72896 406 415 72506 406 413 16499 406 410 60994 406 416 87105 406 413 7438 407 408 14940 408 422 98927 408 426 20705 408 426 37171 409 411 91202 409 420 3403 409 421 94225 409 416 76418 409 424 59424 409 424 72507 409 429 50695 411 427 37818 411 431 61286 411 412 60198 411 417 40107 411 427 82733 411 422 83478 412 418 97128 412 414 83292 412 422 55297 412 416 70121 413 425 36227 413 419 75640 413 431 58016 414 434 40120 414 422 31705 415 428 40871 415 433 61241 416 428 13314 416 424 50066 416 436 65713 416 427 91421 416 429 32189 416 418 60076 416 423 34627 416 435 98771 417 429 51741 417 429 73654 418 426 21615 418 434 46484 419 436 75999 420 434 45109 420 435 11432 420 424 51055 421 438 3937 421 435 76383 422 433 69594 422 439 22455 422 425 11414 422 435 72786 422 435 93472 422 434 72640 423 438 19127 423 433 53662 423 434 37723 424 436 25621 424 439 19965 424 429 80775 424 431 2962 424 437 80773 425 430 9625 425 435 81012 425 433 37229 425 444 58945 425 441 76620 425 441 73587 425 429 5625 426 445 7808 426 435 22159 426 442 53699 426 430 71047 426 435 3388 427 437 57276 427 440 10072 427 445 73709 427 435 42530 427 444 49203 428 431 90826 428 442 91763 428 441 36469 429 443 11158 429 434 81350 429 445 12855 429 438 43180 429 435 88605 429 433 35595 429 447 84634 429 444 71903 430 442 13842 430 450 46606 430 439 8960 430 445 20926 431 441 59382 431 440 88776 431 448 8916 432 449 99227 432 445 7963 432 438 25491 432 452 81202 432 439 41819 432 447 24120 432 436 56192 432 447 93035 432 436 68520 432 439 57929 432 433 11140 432 441 29973 433 445 54722 433 446 11996 433 449 51126 433 447 34840 433 453 6649 433 447 27860 434 447 77042 434 441 49906 434 444 18181 434 450 83946 435 450 18409 435 449 69539 436 451 11983 436 455 90151 436 452 53903 436 446 82274 436 446 27909 437 451 28459 437 445 37452 438 457 87190 438 454 49561 438 443 44025 438 452 66508 438 451 35246 439 441 61955 439 444 51209 439 458 30175 440 448 26170 440 455 15194 440 457 96245 440 442 3977 441 455 64592 441 448 37567 441 443 70844 441 459 52339 441 443 47896 443 445 21251 443 462 60290 444 461 3240 444 450 63935 445 460 76987 445 461 11390 445 452 61033 445 451 19224 445 463 33523 445 461 19834 446 466 3753 446 450 89926 446 464 81545 446 460 90807 446 449 86450 447 455 39316 447 463 36397 447 463 94535 447 459 79902 447 456 12493 448 452 1288 448 466 85088 448 458 31071 449 452 10964 449 451 2034 449 464 14128 449 465 60632 449 454 12782 450 463 16313 450 451 27892 450 458 89297 450 455 63619 450 456 92145 451 456 58063 452 458 29703 452 459 20640 452 469 8095 452 460 20793 452 458 32617 453 458 62392 453 454 7181 453 465 55757 454 469 40861 454 466 10862 455 456 30810 455 458 23994 455 462 42633 455 468 78941 456 461 67030 456 459 24531 456 459 66394 456 460 42368 456 473 56506 456 469 29344 457 465 22384 457 464 56010 457 476 72350 457 460 25402 457 466 71232 457 475 56143 458 476 95361 458 462 51666 458 461 64289 459 463 39385 459 476 64821 459 468 32715 459 474 77039 459 475 42101 460 463 20848 460 464 43932 461 465 34859 461 480 13059 461 473 30620 461 469 57167 461 465 76313 462 467 49337 462 468 32760 462 479 30277 462 472 35409 462 463 43329 462 479 30677 463 472 43743 463 470 32015 463 472 74070 463 481 32378 463 465 25638 464 480 85075 465 473 99051 465 471 7536 465 477 21972 466 479 12289 466 473 52660 466 486 32726 466 476 89848 467 486 40450 467 486 55115 468 477 86686 468 478 13863 469 483 22241 469 488 48476 470 481 33742 470 475 50662 470 476 31375 470 488 72698 470 478 81729 470 490 14160 470 482 30351 471 482 81528 471 475 26371 471 480 17222 471 488 61643 471 483 86128 471 485 34633 471 479 99978 472 480 41949 472 477 7023 472 473 22822 472 480 17555 474 489 65415 474 491 84215 474 487 25367 474 476 54893 474 489 42235 474 493 61164 474 480 37272 475 493 45430 475 481 14532 475 479 15416 475 489 53228 475 486 13041 475 487 55916 476 495 64615 476 479 68890 476 492 19991 476 495 89395 477 495 28091 477 487 66474 477 489 83217 477 491 48526 478 483 77225 478 496 98700 478 484 31551 478 487 20741 478 497 64603 479 481 95346 479 487 50197 479 497 24996 479 488 93196 479 492 60912 479 495 6760 479 496 8828 480 499 59246 480 483 72771 481 487 56069 481 486 64815 481 491 42407 481 500 62552 482 494 96090 482 489 29671 482 492 35744 482 500 66320 482 489 72635 482 492 77824 483 500 13445 483 493 94786 483 493 1775 483 495 99769 483 486 32408 483 499 41673 483 497 49969 483 485 48310 483 489 49838 484 487 28722 484 485 76367 484 500 14033 484 487 65168 484 486 12880 484 499 54974 485 486 49109 485 489 62012 485 498 10568 486 490 34068 486 489 11586 486 489 2737 487 492 34757 487 488 76556 488 500 8460 488 500 52454 488 498 80196 489 490 20358 489 499 2620 489 499 45171 489 491 84217 489 496 28645 490 493 21341 490 493 57047 490 496 30776 491 492 85023 491 500 6960 492 496 45201 493 500 86061 496 497 15360 496 498 10792 496 498 96390 497 500 63493 498 500 85623
예제 출력 D
135350
출처
Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO February 2009 Contest > Gold 3번
알고리즘 분류
해결방법
통과된 코드
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
constexpr long long int INF = INT64_MAX;
long long int disArr[10001][21];
priority_queue<tuple<long long int, int, int>> myPQ;
vector<pair<int, int>> graph[50000];
int N, M, K, U, V, dist, cnt;
int main()
{
ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M >> K;
for (int i = 0; i < M; i++) {
cin >> U >> V >> dist;
// 양방향 도로
graph[U].push_back(make_pair(V, dist));
graph[V].push_back(make_pair(U, dist));
}
// 다익스트라 배열 초기화
for (int i = 1; i <= N; i++)
for (int j = 0; j <= 20; j++)
disArr[i][j] = INF;
// 우선순위 큐에 삽입.
myPQ.push({ 0, 1, 0 }); // < first : 거리 , second : 노드 인덱스 >
disArr[1][0] = 0;
while (!myPQ.empty()) {
// -를 붙이는 이유는 우선순위 큐를 이용하여 정렬하기 위함이다.
// (최소힙으로 구현)
long long int nCost = -get<0>(myPQ.top());
int now = get<1>(myPQ.top());
int cnt = get<2>(myPQ.top()); // 포장개수
myPQ.pop();
// 이미 담겨 있는 것보다 거리가 크면 넘어간다.
if (disArr[now][cnt] < nCost) continue;
// 해당 노드에서 연결된 모든 경로를 확인
for (int i = 0; i < graph[now].size(); i++) {
// disSum = 임시 노드 + 현재 노드에서 i로가는 비용
long long int disSum = nCost + graph[now][i].second;
// 비용이 작다면 최단경로 테이블 값을 갱신.
// 도로가 포장을 안했을 경우
if (disSum < disArr[graph[now][i].first][cnt]) {
// 임시 노드 업데이트
disArr[graph[now][i].first][cnt] = disSum;
// 우선순위 큐에 (거리, 노드 인덱스) 푸시
myPQ.push({ -disSum, graph[now][i].first, cnt});
}
// 비용이 작다면 최단경로 테이블 값을 갱신.
// 도로가 포장을 했을 경우 이동값은 0
// 포장할 수 있는 도로의 개수를 넘으면 안된다.
if (nCost < disArr[graph[now][i].first][cnt + 1] && cnt < K) {
// 임시 노드 업데이트
disArr[graph[now][i].first][cnt + 1] = nCost;
myPQ.push({ -nCost, graph[now][i].first, cnt + 1 });
}
}
}
long long int result = INF;
for (int j = 0; j <= K; j++) result = min(disArr[N][j], result);
cout << result;
return 0;
}
![백준 15657번 (N과 M (8), C++) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og.png)
![백준 1076번 (저항, C++) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og-1.png)
![백준 1929번 (소수 구하기, C++, 에라토스테네스의 체) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/2022/10/boj-og-1-2048x1070-1-1024x535.png)
핑백: 백준 10217번 (KCM Travel, C++, Dijkstra) [BAEKJOON] - 어제와 내일의 나 그 사이의 이야기