백준 1916번 (최소비용 구하기, C++, Dijkstra) / 추가 반례 [BAEKJOON]

최소비용 구하기

https://www.acmicpc.net/problem/1916

시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.5 초128 MB64786202091325732.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

출처

알고리즘 분류


버스 비용은 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;
}

댓글 달기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다

Scroll to Top