최소비용 구하기
https://www.acmicpc.net/problem/1916
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 128 MB | 64786 | 20209 | 13257 | 32.113% |
문제
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다.
우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다.
A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라.
도시의 번호는 1부터 N까지이다.
입력
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다.
그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다.
먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다.
그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다.
버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.
출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
예제 입력 1
5 8 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 1 5
예제 출력 1
4
예제 입력 A
2 1 1 2 0 1 2
예제 출력 A
0
예제 입력 B
4 3 2 1 1 1 3 1 3 4 1 2 4
예제 출력 B
3
예제 입력 C
1000 999 1 2 99999 2 3 99999 3 4 99999 4 5 99999 5 6 99999 6 7 99999 7 8 99999 8 9 99999 9 10 99999 10 11 99999 11 12 99999 12 13 99999 13 14 99999 14 15 99999 15 16 99999 16 17 99999 17 18 99999 18 19 99999 19 20 99999 20 21 99999 21 22 99999 22 23 99999 23 24 99999 24 25 99999 25 26 99999 26 27 99999 27 28 99999 28 29 99999 29 30 99999 30 31 99999 31 32 99999 32 33 99999 33 34 99999 34 35 99999 35 36 99999 36 37 99999 37 38 99999 38 39 99999 39 40 99999 40 41 99999 41 42 99999 42 43 99999 43 44 99999 44 45 99999 45 46 99999 46 47 99999 47 48 99999 48 49 99999 49 50 99999 50 51 99999 51 52 99999 52 53 99999 53 54 99999 54 55 99999 55 56 99999 56 57 99999 57 58 99999 58 59 99999 59 60 99999 60 61 99999 61 62 99999 62 63 99999 63 64 99999 64 65 99999 65 66 99999 66 67 99999 67 68 99999 68 69 99999 69 70 99999 70 71 99999 71 72 99999 72 73 99999 73 74 99999 74 75 99999 75 76 99999 76 77 99999 77 78 99999 78 79 99999 79 80 99999 80 81 99999 81 82 99999 82 83 99999 83 84 99999 84 85 99999 85 86 99999 86 87 99999 87 88 99999 88 89 99999 89 90 99999 90 91 99999 91 92 99999 92 93 99999 93 94 99999 94 95 99999 95 96 99999 96 97 99999 97 98 99999 98 99 99999 99 100 99999 100 101 99999 101 102 99999 102 103 99999 103 104 99999 104 105 99999 105 106 99999 106 107 99999 107 108 99999 108 109 99999 109 110 99999 110 111 99999 111 112 99999 112 113 99999 113 114 99999 114 115 99999 115 116 99999 116 117 99999 117 118 99999 118 119 99999 119 120 99999 120 121 99999 121 122 99999 122 123 99999 123 124 99999 124 125 99999 125 126 99999 126 127 99999 127 128 99999 128 129 99999 129 130 99999 130 131 99999 131 132 99999 132 133 99999 133 134 99999 134 135 99999 135 136 99999 136 137 99999 137 138 99999 138 139 99999 139 140 99999 140 141 99999 141 142 99999 142 143 99999 143 144 99999 144 145 99999 145 146 99999 146 147 99999 147 148 99999 148 149 99999 149 150 99999 150 151 99999 151 152 99999 152 153 99999 153 154 99999 154 155 99999 155 156 99999 156 157 99999 157 158 99999 158 159 99999 159 160 99999 160 161 99999 161 162 99999 162 163 99999 163 164 99999 164 165 99999 165 166 99999 166 167 99999 167 168 99999 168 169 99999 169 170 99999 170 171 99999 171 172 99999 172 173 99999 173 174 99999 174 175 99999 175 176 99999 176 177 99999 177 178 99999 178 179 99999 179 180 99999 180 181 99999 181 182 99999 182 183 99999 183 184 99999 184 185 99999 185 186 99999 186 187 99999 187 188 99999 188 189 99999 189 190 99999 190 191 99999 191 192 99999 192 193 99999 193 194 99999 194 195 99999 195 196 99999 196 197 99999 197 198 99999 198 199 99999 199 200 99999 200 201 99999 201 202 99999 202 203 99999 203 204 99999 204 205 99999 205 206 99999 206 207 99999 207 208 99999 208 209 99999 209 210 99999 210 211 99999 211 212 99999 212 213 99999 213 214 99999 214 215 99999 215 216 99999 216 217 99999 217 218 99999 218 219 99999 219 220 99999 220 221 99999 221 222 99999 222 223 99999 223 224 99999 224 225 99999 225 226 99999 226 227 99999 227 228 99999 228 229 99999 229 230 99999 230 231 99999 231 232 99999 232 233 99999 233 234 99999 234 235 99999 235 236 99999 236 237 99999 237 238 99999 238 239 99999 239 240 99999 240 241 99999 241 242 99999 242 243 99999 243 244 99999 244 245 99999 245 246 99999 246 247 99999 247 248 99999 248 249 99999 249 250 99999 250 251 99999 251 252 99999 252 253 99999 253 254 99999 254 255 99999 255 256 99999 256 257 99999 257 258 99999 258 259 99999 259 260 99999 260 261 99999 261 262 99999 262 263 99999 263 264 99999 264 265 99999 265 266 99999 266 267 99999 267 268 99999 268 269 99999 269 270 99999 270 271 99999 271 272 99999 272 273 99999 273 274 99999 274 275 99999 275 276 99999 276 277 99999 277 278 99999 278 279 99999 279 280 99999 280 281 99999 281 282 99999 282 283 99999 283 284 99999 284 285 99999 285 286 99999 286 287 99999 287 288 99999 288 289 99999 289 290 99999 290 291 99999 291 292 99999 292 293 99999 293 294 99999 294 295 99999 295 296 99999 296 297 99999 297 298 99999 298 299 99999 299 300 99999 300 301 99999 301 302 99999 302 303 99999 303 304 99999 304 305 99999 305 306 99999 306 307 99999 307 308 99999 308 309 99999 309 310 99999 310 311 99999 311 312 99999 312 313 99999 313 314 99999 314 315 99999 315 316 99999 316 317 99999 317 318 99999 318 319 99999 319 320 99999 320 321 99999 321 322 99999 322 323 99999 323 324 99999 324 325 99999 325 326 99999 326 327 99999 327 328 99999 328 329 99999 329 330 99999 330 331 99999 331 332 99999 332 333 99999 333 334 99999 334 335 99999 335 336 99999 336 337 99999 337 338 99999 338 339 99999 339 340 99999 340 341 99999 341 342 99999 342 343 99999 343 344 99999 344 345 99999 345 346 99999 346 347 99999 347 348 99999 348 349 99999 349 350 99999 350 351 99999 351 352 99999 352 353 99999 353 354 99999 354 355 99999 355 356 99999 356 357 99999 357 358 99999 358 359 99999 359 360 99999 360 361 99999 361 362 99999 362 363 99999 363 364 99999 364 365 99999 365 366 99999 366 367 99999 367 368 99999 368 369 99999 369 370 99999 370 371 99999 371 372 99999 372 373 99999 373 374 99999 374 375 99999 375 376 99999 376 377 99999 377 378 99999 378 379 99999 379 380 99999 380 381 99999 381 382 99999 382 383 99999 383 384 99999 384 385 99999 385 386 99999 386 387 99999 387 388 99999 388 389 99999 389 390 99999 390 391 99999 391 392 99999 392 393 99999 393 394 99999 394 395 99999 395 396 99999 396 397 99999 397 398 99999 398 399 99999 399 400 99999 400 401 99999 401 402 99999 402 403 99999 403 404 99999 404 405 99999 405 406 99999 406 407 99999 407 408 99999 408 409 99999 409 410 99999 410 411 99999 411 412 99999 412 413 99999 413 414 99999 414 415 99999 415 416 99999 416 417 99999 417 418 99999 418 419 99999 419 420 99999 420 421 99999 421 422 99999 422 423 99999 423 424 99999 424 425 99999 425 426 99999 426 427 99999 427 428 99999 428 429 99999 429 430 99999 430 431 99999 431 432 99999 432 433 99999 433 434 99999 434 435 99999 435 436 99999 436 437 99999 437 438 99999 438 439 99999 439 440 99999 440 441 99999 441 442 99999 442 443 99999 443 444 99999 444 445 99999 445 446 99999 446 447 99999 447 448 99999 448 449 99999 449 450 99999 450 451 99999 451 452 99999 452 453 99999 453 454 99999 454 455 99999 455 456 99999 456 457 99999 457 458 99999 458 459 99999 459 460 99999 460 461 99999 461 462 99999 462 463 99999 463 464 99999 464 465 99999 465 466 99999 466 467 99999 467 468 99999 468 469 99999 469 470 99999 470 471 99999 471 472 99999 472 473 99999 473 474 99999 474 475 99999 475 476 99999 476 477 99999 477 478 99999 478 479 99999 479 480 99999 480 481 99999 481 482 99999 482 483 99999 483 484 99999 484 485 99999 485 486 99999 486 487 99999 487 488 99999 488 489 99999 489 490 99999 490 491 99999 491 492 99999 492 493 99999 493 494 99999 494 495 99999 495 496 99999 496 497 99999 497 498 99999 498 499 99999 499 500 99999 500 501 99999 501 502 99999 502 503 99999 503 504 99999 504 505 99999 505 506 99999 506 507 99999 507 508 99999 508 509 99999 509 510 99999 510 511 99999 511 512 99999 512 513 99999 513 514 99999 514 515 99999 515 516 99999 516 517 99999 517 518 99999 518 519 99999 519 520 99999 520 521 99999 521 522 99999 522 523 99999 523 524 99999 524 525 99999 525 526 99999 526 527 99999 527 528 99999 528 529 99999 529 530 99999 530 531 99999 531 532 99999 532 533 99999 533 534 99999 534 535 99999 535 536 99999 536 537 99999 537 538 99999 538 539 99999 539 540 99999 540 541 99999 541 542 99999 542 543 99999 543 544 99999 544 545 99999 545 546 99999 546 547 99999 547 548 99999 548 549 99999 549 550 99999 550 551 99999 551 552 99999 552 553 99999 553 554 99999 554 555 99999 555 556 99999 556 557 99999 557 558 99999 558 559 99999 559 560 99999 560 561 99999 561 562 99999 562 563 99999 563 564 99999 564 565 99999 565 566 99999 566 567 99999 567 568 99999 568 569 99999 569 570 99999 570 571 99999 571 572 99999 572 573 99999 573 574 99999 574 575 99999 575 576 99999 576 577 99999 577 578 99999 578 579 99999 579 580 99999 580 581 99999 581 582 99999 582 583 99999 583 584 99999 584 585 99999 585 586 99999 586 587 99999 587 588 99999 588 589 99999 589 590 99999 590 591 99999 591 592 99999 592 593 99999 593 594 99999 594 595 99999 595 596 99999 596 597 99999 597 598 99999 598 599 99999 599 600 99999 600 601 99999 601 602 99999 602 603 99999 603 604 99999 604 605 99999 605 606 99999 606 607 99999 607 608 99999 608 609 99999 609 610 99999 610 611 99999 611 612 99999 612 613 99999 613 614 99999 614 615 99999 615 616 99999 616 617 99999 617 618 99999 618 619 99999 619 620 99999 620 621 99999 621 622 99999 622 623 99999 623 624 99999 624 625 99999 625 626 99999 626 627 99999 627 628 99999 628 629 99999 629 630 99999 630 631 99999 631 632 99999 632 633 99999 633 634 99999 634 635 99999 635 636 99999 636 637 99999 637 638 99999 638 639 99999 639 640 99999 640 641 99999 641 642 99999 642 643 99999 643 644 99999 644 645 99999 645 646 99999 646 647 99999 647 648 99999 648 649 99999 649 650 99999 650 651 99999 651 652 99999 652 653 99999 653 654 99999 654 655 99999 655 656 99999 656 657 99999 657 658 99999 658 659 99999 659 660 99999 660 661 99999 661 662 99999 662 663 99999 663 664 99999 664 665 99999 665 666 99999 666 667 99999 667 668 99999 668 669 99999 669 670 99999 670 671 99999 671 672 99999 672 673 99999 673 674 99999 674 675 99999 675 676 99999 676 677 99999 677 678 99999 678 679 99999 679 680 99999 680 681 99999 681 682 99999 682 683 99999 683 684 99999 684 685 99999 685 686 99999 686 687 99999 687 688 99999 688 689 99999 689 690 99999 690 691 99999 691 692 99999 692 693 99999 693 694 99999 694 695 99999 695 696 99999 696 697 99999 697 698 99999 698 699 99999 699 700 99999 700 701 99999 701 702 99999 702 703 99999 703 704 99999 704 705 99999 705 706 99999 706 707 99999 707 708 99999 708 709 99999 709 710 99999 710 711 99999 711 712 99999 712 713 99999 713 714 99999 714 715 99999 715 716 99999 716 717 99999 717 718 99999 718 719 99999 719 720 99999 720 721 99999 721 722 99999 722 723 99999 723 724 99999 724 725 99999 725 726 99999 726 727 99999 727 728 99999 728 729 99999 729 730 99999 730 731 99999 731 732 99999 732 733 99999 733 734 99999 734 735 99999 735 736 99999 736 737 99999 737 738 99999 738 739 99999 739 740 99999 740 741 99999 741 742 99999 742 743 99999 743 744 99999 744 745 99999 745 746 99999 746 747 99999 747 748 99999 748 749 99999 749 750 99999 750 751 99999 751 752 99999 752 753 99999 753 754 99999 754 755 99999 755 756 99999 756 757 99999 757 758 99999 758 759 99999 759 760 99999 760 761 99999 761 762 99999 762 763 99999 763 764 99999 764 765 99999 765 766 99999 766 767 99999 767 768 99999 768 769 99999 769 770 99999 770 771 99999 771 772 99999 772 773 99999 773 774 99999 774 775 99999 775 776 99999 776 777 99999 777 778 99999 778 779 99999 779 780 99999 780 781 99999 781 782 99999 782 783 99999 783 784 99999 784 785 99999 785 786 99999 786 787 99999 787 788 99999 788 789 99999 789 790 99999 790 791 99999 791 792 99999 792 793 99999 793 794 99999 794 795 99999 795 796 99999 796 797 99999 797 798 99999 798 799 99999 799 800 99999 800 801 99999 801 802 99999 802 803 99999 803 804 99999 804 805 99999 805 806 99999 806 807 99999 807 808 99999 808 809 99999 809 810 99999 810 811 99999 811 812 99999 812 813 99999 813 814 99999 814 815 99999 815 816 99999 816 817 99999 817 818 99999 818 819 99999 819 820 99999 820 821 99999 821 822 99999 822 823 99999 823 824 99999 824 825 99999 825 826 99999 826 827 99999 827 828 99999 828 829 99999 829 830 99999 830 831 99999 831 832 99999 832 833 99999 833 834 99999 834 835 99999 835 836 99999 836 837 99999 837 838 99999 838 839 99999 839 840 99999 840 841 99999 841 842 99999 842 843 99999 843 844 99999 844 845 99999 845 846 99999 846 847 99999 847 848 99999 848 849 99999 849 850 99999 850 851 99999 851 852 99999 852 853 99999 853 854 99999 854 855 99999 855 856 99999 856 857 99999 857 858 99999 858 859 99999 859 860 99999 860 861 99999 861 862 99999 862 863 99999 863 864 99999 864 865 99999 865 866 99999 866 867 99999 867 868 99999 868 869 99999 869 870 99999 870 871 99999 871 872 99999 872 873 99999 873 874 99999 874 875 99999 875 876 99999 876 877 99999 877 878 99999 878 879 99999 879 880 99999 880 881 99999 881 882 99999 882 883 99999 883 884 99999 884 885 99999 885 886 99999 886 887 99999 887 888 99999 888 889 99999 889 890 99999 890 891 99999 891 892 99999 892 893 99999 893 894 99999 894 895 99999 895 896 99999 896 897 99999 897 898 99999 898 899 99999 899 900 99999 900 901 99999 901 902 99999 902 903 99999 903 904 99999 904 905 99999 905 906 99999 906 907 99999 907 908 99999 908 909 99999 909 910 99999 910 911 99999 911 912 99999 912 913 99999 913 914 99999 914 915 99999 915 916 99999 916 917 99999 917 918 99999 918 919 99999 919 920 99999 920 921 99999 921 922 99999 922 923 99999 923 924 99999 924 925 99999 925 926 99999 926 927 99999 927 928 99999 928 929 99999 929 930 99999 930 931 99999 931 932 99999 932 933 99999 933 934 99999 934 935 99999 935 936 99999 936 937 99999 937 938 99999 938 939 99999 939 940 99999 940 941 99999 941 942 99999 942 943 99999 943 944 99999 944 945 99999 945 946 99999 946 947 99999 947 948 99999 948 949 99999 949 950 99999 950 951 99999 951 952 99999 952 953 99999 953 954 99999 954 955 99999 955 956 99999 956 957 99999 957 958 99999 958 959 99999 959 960 99999 960 961 99999 961 962 99999 962 963 99999 963 964 99999 964 965 99999 965 966 99999 966 967 99999 967 968 99999 968 969 99999 969 970 99999 970 971 99999 971 972 99999 972 973 99999 973 974 99999 974 975 99999 975 976 99999 976 977 99999 977 978 99999 978 979 99999 979 980 99999 980 981 99999 981 982 99999 982 983 99999 983 984 99999 984 985 99999 985 986 99999 986 987 99999 987 988 99999 988 989 99999 989 990 99999 990 991 99999 991 992 99999 992 993 99999 993 994 99999 994 995 99999 995 996 99999 996 997 99999 997 998 99999 998 999 99999 999 1000 99999 1 1000
예제 출력 C
99899001
출처
- 데이터를 추가한 사람: djm03178, qf9ar8nv, sait2000
- 시간 제한을 수정한 사람: djm03178
- 문제의 오타를 찾은 사람: HowlingOfSouL, ibjsw
- 잘못된 데이터를 찾은 사람: hsnks100
- 빠진 조건을 찾은 사람: jh05013, luke0201, toysmars
알고리즘 분류
버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수
=> 버스의 비용이 0 인 경우가 존재한다는 것에 주의
추가적으로 현재 임시노드보다 거리가 크다면 넘어간다 (없으면 시간초과 발생)
통과된 코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
constexpr int MAXN = 10001;
constexpr int INF = INT32_MAX;
// Dijkstra 알고리즘에 사용할 우선순위 큐
priority_queue<pair<int, int>> myPQ;
///*
//각 노드에 연결되어 있는 노드에 대한 정보를 담는 벡터
//a번 노드에서 b번 노드로 가는 비용이 c라는 의미
//graph[a].push_back((make_pair(B, C));
//*/
vector<pair<int, int>> graph[MAXN];
// 임시노드
int disArr[MAXN];
// N : 도시의 개수, M : 간선의 개수, K : 시작 노드, E : 도착 노드
// u : 현재 노드, v : 이웃 노드, dist : 거리
int N, M, K, E, u, v, dist;
void Dijkstra(int start)
{
// 임시배열 초기화
for (int i = 1; i <= N; i++) disArr[i] = INF;
// 우선순위 큐에 삽입.
myPQ.push({ 0, start }); // < first : 거리 , second : 노드 인덱스 >
disArr[start] = 0;
while (!myPQ.empty()) {
// -를 붙이는 이유는 우선순위 큐를 이용하여 정렬하기 위함이다.
// (최소힙으로 구현)
int nCost = -myPQ.top().first;
int now = myPQ.top().second;
myPQ.pop();
// 이미 담겨 있는 것보다 거리가 크면 넘어간다.
if (disArr[now] < nCost) continue;
// 해당 노드에서 연결된 모든 경로를 확인
for (int i = 0; i < graph[now].size(); i++) {
// disSum = 임시 노드 + 현재 노드에서 i로가는 비용
int disSum = nCost + graph[now][i].second;
// 비용이 작다면 최단경로 테이블 값을 갱신.
if (disSum < disArr[graph[now][i].first]) {
// 임시 노드 업데이트
disArr[graph[now][i].first] = disSum;
// 우선순위 큐에 (거리, 노드 인덱스) 푸시
myPQ.push(make_pair(-disSum, graph[now][i].first));
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
cin.tie(NULL);
cout.tie(NULL);
// N 정점의 개수, E 간선의 개수를 입력받는다.
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> u >> v >> dist;
graph[u].push_back(make_pair(v, dist));
}
cin >> K >> E;
Dijkstra(K);
cout << disArr[E];
return 0;
}
![백준 2206번 (벽 부수고 이동하기, C++) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og.png)
![백준 1162번 (도로포장, C++, Dijkstra) / 추가 반례 [BAEKJOON]](https://lycos7560.com/wp-content/uploads/2022/10/boj-og-1-2048x1070-1-1024x535.png)
![백준 21955번 (Split, C++) [BAEKJOON]](https://lycos7560.com/wp-content/uploads/boj-og-1.png)