거의 최단 경로

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

문제

요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다.

네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다.

하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다.

상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다.

이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다.

거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 

예를 들어, 도로 지도가 아래와 같을 때를 생각해보자.

원은 장소를 의미하고, 선은 단방향 도로를 나타낸다.

시작점은 S, 도착점은 D로 표시되어 있다. 굵은 선은 최단 경로를 나타낸다. (아래 그림에 최단 경로는 두 개가 있다)

거의 최단 경로는 점선으로 표시된 경로이다.

이 경로는 최단 경로에 포함되지 않은 도로로 이루어진 경로 중 가장 짧은 경로이다.

거의 최단 경로는 여러 개 존재할 수도 있다.

예를 들어, 아래 그림의 길이가 3인 도로의 길이가 1이라면, 거의 최단 경로는 두 개가 된다.

또, 거의 최단 경로가 없는 경우도 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 10⁴)가 주어진다.

장소는 0부터 N-1번까지 번호가 매겨져 있다. 둘째 줄에는 시작점 S와 도착점 D가 주어진다. (S ≠ D; 0 ≤ S, D < N)

다음 M개 줄에는 도로의 정보 U, V, P가 주어진다. (U ≠ V ; 0 ≤ U, V < N; 1 ≤ P ≤ 10³)

이 뜻은 U에서 V로 가는 도로의 길이가 P라는 뜻이다.

U에서 V로 가는 도로는 최대 한 개이다.

또, U에서 V로 가는 도로와 V에서 U로 가는 도로는 다른 도로이다. 

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 거의 최단 경로의 길이를 출력한다.

만약, 거의 최단 경로가 없는 경우에는 -1을 출력한다.

예제 출력 1

7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0

예제 입력 1

5
-1
6

출처

ICPC > Regionals > Latin America > South America Regional Contests 2008 A번

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: gkswjdzz, sait2000, smsm8111
• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 데이크스트라

추가 예제

예제 출력 A

100 765
44 52
0 11 939
0 18 635
0 26 757
0 39 558
0 41 669
0 43 855
0 45 951
0 46 755
0 51 785
0 52 218
0 78 557
0 94 918
0 96 300
1 19 752
1 22 157
1 31 797
1 37 871
1 78 834
2 0 275
2 30 73
2 64 32
2 67 552
2 78 7
2 81 883
2 96 315
2 99 865
3 11 299
3 13 196
3 37 247
3 45 523
3 47 745
3 54 474
3 60 63
3 94 244
3 97 699
3 99 855
4 10 516
4 17 506
4 24 985
4 28 598
4 35 598
4 39 744
4 44 749
4 46 8
4 77 363
4 78 618
4 92 988
4 97 591
5 0 918
5 9 8
5 14 405
5 23 448
5 84 354
6 0 404
6 10 209
6 20 352
6 57 651
6 71 490
6 77 934
6 94 188
6 96 638
6 99 138
7 25 815
7 27 55
7 42 606
7 56 643
7 65 966
7 81 755
8 0 684
8 5 959
8 13 998
8 19 757
8 22 172
8 33 638
8 38 777
8 51 185
8 59 321
8 67 403
8 69 475
8 71 204
8 74 567
8 97 138
9 15 965
9 17 611
9 64 712
9 66 743
9 84 971
10 5 486
11 3 678
11 54 838
11 86 226
11 95 623
12 5 427
12 28 19
12 33 879
12 35 876
12 37 907
12 50 437
12 51 853
12 52 407
12 58 756
12 68 480
12 75 867
12 85 833
13 6 356
13 37 954
13 53 479
13 68 448
13 74 707
13 79 369
13 80 735
13 84 17
13 96 355
14 6 185
14 12 121
14 17 925
14 32 276
14 36 559
14 39 343
14 44 90
14 86 513
14 87 952
14 96 912
15 13 296
15 20 726
15 36 835
15 41 458
15 49 17
15 57 47
15 61 583
15 65 25
15 82 703
16 9 289
16 19 289
16 26 935
16 46 122
16 58 611
16 59 625
16 60 89
16 75 674
16 81 147
16 85 806
16 86 89
17 7 848
17 39 490
17 53 980
17 58 372
17 62 357
17 78 885
17 83 406
17 87 873
17 95 32
18 41 232
18 43 394
18 47 35
18 50 697
18 83 464
18 87 281
19 1 857
19 12 589
19 14 819
19 37 470
19 40 520
19 42 276
19 43 27
19 66 706
19 71 426
19 83 858
19 94 353
20 13 523
20 17 128
20 51 90
20 53 411
20 84 903
20 91 747
20 96 503
21 23 721
21 27 724
21 28 34
21 30 396
21 34 86
21 37 371
21 53 371
21 54 672
22 4 325
22 11 407
22 44 631
22 55 480
22 68 861
22 90 338
23 1 109
23 15 850
23 34 645
23 48 582
23 52 264
23 58 330
23 64 796
23 65 118
23 69 133
23 89 389
24 11 220
24 26 5
24 38 951
24 44 990
24 45 123
24 49 216
24 51 505
24 90 388
24 93 475
25 24 633
25 41 489
25 83 434
26 4 577
26 17 977
26 19 558
26 31 863
26 33 284
26 43 751
26 46 576
26 48 224
26 79 497
27 14 26
27 18 949
27 21 102
27 38 357
27 45 528
27 75 614
27 76 289
27 80 803
27 81 343
28 3 458
28 15 893
28 24 579
28 44 649
28 62 934
28 65 964
28 67 177
28 87 678
29 0 191
29 39 112
29 45 184
29 61 778
29 87 810
30 4 335
30 11 829
30 50 996
30 54 470
30 60 972
30 63 147
30 98 559
30 99 24
31 15 30
31 29 250
31 46 53
31 63 488
31 71 561
32 35 812
32 50 781
32 67 540
33 34 611
33 56 12
33 61 631
33 64 842
33 89 697
34 4 208
34 19 621
34 23 343
34 35 129
34 40 489
34 42 323
34 56 762
34 64 522
34 79 412
35 1 64
35 3 799
35 5 360
35 6 488
35 11 879
35 27 403
35 28 320
35 43 802
35 71 639
35 75 147
35 94 310
36 3 471
36 18 920
36 37 260
36 51 987
36 68 888
36 77 573
37 5 79
37 24 306
37 51 731
37 54 451
38 34 359
38 35 854
38 48 903
38 71 322
38 99 262
39 5 40
39 6 830
39 8 58
39 22 757
39 23 539
39 36 984
39 58 75
39 60 780
39 63 223
39 65 365
39 66 86
39 67 953
39 78 705
39 79 505
39 87 29
39 94 31
39 97 865
40 11 60
40 49 145
40 57 211
40 60 371
40 81 144
40 82 874
40 97 994
41 37 142
41 99 976
42 4 376
42 8 56
42 12 372
42 28 634
42 30 71
42 35 766
42 43 653
42 45 283
42 47 674
42 52 807
42 57 189
42 84 279
42 86 366
42 91 728
42 93 702
43 6 149
43 14 39
43 40 796
43 87 35
43 89 946
43 94 259
43 95 375
44 8 35
44 21 605
44 25 809
44 73 418
44 85 914
44 93 368
45 34 90
45 41 172
45 48 253
45 53 829
45 65 31
45 86 994
45 92 826
46 18 346
46 37 161
46 44 505
46 76 992
46 80 576
46 94 984
47 8 295
47 35 330
47 56 954
47 76 158
47 77 39
47 80 313
47 82 217
47 87 688
48 17 214
48 31 760
48 36 989
48 37 922
48 84 886
49 12 757
49 14 724
49 16 948
49 34 854
49 38 552
49 40 361
49 50 990
49 53 148
49 74 959
49 82 226
49 84 153
49 87 134
50 14 838
50 33 260
50 37 624
50 44 381
50 47 868
50 55 616
50 90 135
50 92 148
50 97 510
51 56 459
51 84 726
51 91 543
51 99 855
52 2 872
52 23 771
52 35 380
52 76 773
52 81 769
53 10 314
53 48 745
53 49 567
53 50 99
53 58 180
53 67 297
53 80 107
54 17 458
54 21 310
54 44 68
54 70 896
54 83 986
54 87 605
54 90 422
55 0 101
55 7 868
55 31 316
55 36 208
55 46 151
55 87 612
56 0 40
56 16 247
56 35 492
56 59 609
56 73 796
56 78 225
57 2 419
57 17 785
57 23 523
57 37 730
57 42 290
57 47 503
57 59 909
57 81 319
57 84 782
57 95 250
58 2 842
58 26 886
58 52 168
58 56 386
58 59 253
58 70 174
58 79 608
58 81 764
58 89 215
59 8 105
59 9 876
59 18 305
59 20 397
59 31 278
59 35 379
59 57 702
60 18 785
60 59 603
60 62 224
60 63 300
60 69 111
60 70 437
60 86 129
60 88 862
60 90 603
61 13 185
61 14 521
61 26 23
61 33 645
61 45 907
61 67 269
61 75 717
61 82 919
61 90 554
61 91 865
61 98 182
62 13 135
62 24 96
62 39 625
62 63 901
62 81 816
62 97 592
63 7 518
63 8 46
63 16 724
63 52 912
63 97 725
64 15 554
64 29 395
64 35 177
64 38 340
64 58 100
64 66 570
64 76 754
65 24 370
65 29 726
65 33 348
65 41 388
65 44 931
65 59 293
65 92 255
65 95 937
66 7 435
66 17 260
66 19 510
66 23 571
66 25 875
66 39 671
66 77 97
66 80 52
66 82 939
67 2 110
67 40 346
67 41 641
67 46 881
67 52 703
67 58 770
67 62 974
67 81 199
67 90 396
67 95 558
67 96 375
67 99 597
68 2 395
68 17 863
68 20 8
68 22 682
68 43 444
68 74 870
68 79 739
68 98 158
69 10 763
69 13 933
69 25 738
69 28 755
69 33 745
69 53 998
69 58 961
69 78 410
69 89 621
69 90 271
69 91 362
69 98 574
70 17 788
70 38 695
70 44 383
70 55 843
70 60 373
70 61 529
71 7 932
71 9 184
71 25 341
71 27 360
71 53 832
71 60 135
71 64 245
71 69 980
71 72 238
71 74 210
72 14 63
72 42 346
72 60 204
72 71 324
72 73 970
72 88 547
72 90 618
73 9 20
73 17 980
73 18 845
73 27 728
73 37 577
73 46 472
73 56 825
73 58 111
73 61 962
73 75 69
73 86 389
74 10 720
74 17 31
74 67 163
74 69 621
74 79 831
74 84 479
74 88 579
74 91 43
75 18 763
75 24 669
75 33 618
75 61 689
75 78 430
75 83 422
76 1 768
76 31 972
76 69 445
76 73 111
76 75 841
76 78 529
76 86 614
76 91 841
77 5 158
77 14 396
77 20 358
77 37 436
77 51 954
77 52 316
77 55 782
77 88 65
77 99 451
78 9 753
78 38 838
78 91 373
79 23 788
79 30 901
79 48 428
79 84 193
79 85 396
79 88 456
80 6 442
80 10 869
80 29 590
80 32 894
80 45 429
80 67 2
80 74 800
80 90 257
81 12 6
81 27 306
81 35 908
81 68 610
81 69 629
81 78 320
81 88 385
81 90 337
81 96 483
82 30 690
82 53 871
82 61 713
82 97 228
82 99 199
83 34 654
83 39 786
83 46 529
83 53 429
83 76 995
83 82 802
83 84 571
84 0 362
84 6 696
84 19 298
84 30 741
84 34 286
84 54 31
84 58 194
84 61 383
84 81 487
84 88 656
84 95 750
84 98 916
84 99 819
85 6 716
85 38 723
85 43 889
85 44 775
85 57 115
85 68 548
85 77 480
86 23 988
86 41 963
86 49 512
86 62 210
86 89 363
86 92 738
86 96 942
87 7 666
87 22 689
87 26 53
87 50 675
87 54 297
87 82 997
87 83 883
88 23 942
88 43 622
88 52 24
88 61 777
88 63 58
88 79 708
88 92 637
89 19 853
89 29 912
89 42 95
90 16 517
90 18 18
90 19 115
90 40 979
90 56 780
90 84 13
90 86 926
91 15 816
91 17 998
91 32 554
91 39 131
91 44 928
91 59 707
91 70 288
91 75 906
92 16 936
92 35 45
92 46 541
92 51 871
92 55 982
92 63 362
92 70 453
92 72 376
92 75 370
92 79 973
92 96 986
93 3 705
93 15 801
93 23 894
93 49 26
93 50 974
93 56 925
93 94 558
94 0 893
94 33 130
94 34 520
94 35 382
94 47 352
94 50 1
94 56 922
94 57 844
94 62 854
94 79 87
95 33 836
95 36 728
95 46 558
95 57 134
95 73 232
95 75 191
96 17 846
96 72 506
97 11 623
97 46 668
97 60 739
97 63 937
97 86 2
97 95 87
98 22 60
98 25 409
98 53 509
98 61 96
98 83 660
98 86 889
99 45 624
99 47 589
99 51 300
99 58 248
99 77 867
99 78 769
99 80 566
0 0

예제 출력 A

726

예제 입력 B

4 5
0 2
0 1 1
0 3 5
1 2 1
1 3 1
3 2 1
4 5
0 2
0 1 1
0 3 5
1 2 2
1 3 1
3 2 1
4 5
0 2
0 1 5
0 3 1
1 2 1
3 1 1
3 2 2
5 6
0 1
0 1 1
0 2 1
0 4 1
2 3 1
3 1 1
4 1 2
0 0

예제 출력 B

6
-1
-1
3

예제 입력 C

5 6
0 1
0 1 1
0 2 1
0 4 1
2 3 1
3 1 1
4 1 1
5 6
0 1
0 1 3
0 2 1
0 4 1
2 3 1
3 1 1
4 1 2
4 6
0 3
0 1 1
0 2 1
1 0 1
1 2 1
2 0 1
2 1 1
3 6
0 2
0 1 1
0 2 1
1 0 1
1 2 1
2 0 1
2 1 1
0 0

예제 출력 C

2
-1
-1
2

예제 입력 D

3 2
0 2
0 1 1
1 2 1
5 6
0 1
0 1 1
0 2 1
2 3 1
2 4 1
3 1 1
4 1 1
4 6
0 3
0 1 1
0 2 1
0 3 1
1 2 1
1 3 1
2 3 1
4 6
0 3
0 1 1
0 2 2
0 3 3
1 2 1
1 3 2
2 3 1
0 0

예제 출력 D

-1
3
2
-1

틀린 코드 (메모리 초과)

다익스트라의 경로를 저장하기 위하여 우선 순위 큐에 지나온 정점들을 list<pair<int, int>>에 담아 보았다.

당연하게 메모리 초과 (정답은 잘나온다… ㅜㅜ)

원리는 list에 있는 정점들을 방문처리하여 다음 다익스트라를 사용할 때 넘기는 방법을 사용했다.

#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <tuple>
#include <map>

using namespace std;

constexpr int INF = INT32_MAX;

int disArr[501];

bool check[501][501];

int N, M, S, D, U, V, P;

int Dijstra()
{
    int result = INF;

    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            check[i][j] = false;
        }
    }

    // 임시배열 초기화
    for (int i = 0; i <= N; i++) disArr[i] = INF;

    priority_queue<tuple<int, int, list<pair<int, int>>>> firstPQ;

    vector<pair<int, int>> graph[10000];

    list<pair<int, int>> myList;

    multimap<int, list<pair<int, int>>> myMap;

    for (int i = 0; i < M; i++) {
        cin >> U >> V >> P;
        graph[U].push_back(make_pair(V, P));
    }

    // 우선순위 큐에 삽입.
    firstPQ.push({ 0, S, myList }); // < first : 거리 , second : 노드 인덱스 >
    disArr[S] = 0;
    while (!firstPQ.empty()) {
        // -를 붙이는 이유는 우선순위 큐를 이용하여 정렬하기 위함이다.
        // (최소힙으로 구현)
        int nCost = -get<0>(firstPQ.top());
        int now = get<1>(firstPQ.top());
        myList = get<2>(firstPQ.top());
        firstPQ.pop();

        // 이미 담겨 있는 것보다 거리가 크면 넘어간다.
        if (disArr[now] < nCost) continue;

        // 해당 노드에서 연결된 모든 경로를 확인
        for (int i = 0; i < graph[now].size(); i++) {
            list<pair<int, int>> tempList = myList;
            // disSum = 임시 노드 + 현재 노드에서 i로가는 비용
            int disSum = nCost + graph[now][i].second;

            // 비용이 더 작다면 최단경로 테이블 값을 갱신.
            if (disSum <= disArr[graph[now][i].first]) {
                tempList.push_back(make_pair(now, graph[now][i].first));

                if (graph[now][i].first == D && result >= disSum) {
                    result = disSum;
                    myMap.insert(make_pair(disSum, tempList));
                }

                // 임시 노드 업데이트
                disArr[graph[now][i].first] = disSum;
                // 우선순위 큐에 (거리, 노드 인덱스) 푸시
                firstPQ.push(make_tuple(-disSum, graph[now][i].first, tempList));
            }
        }
    }

    result = disArr[D];

    for (auto mit = myMap.begin(); mit != myMap.end(); mit++) {
        if (result == mit->first) {
            for (auto it = mit->second.begin(); it != mit->second.end(); it++) {
                check[it->first][it->second] = true;
            }
        }

        else break;
    }

    priority_queue<pair<int, int>> myPQ;

    // 임시배열 초기화
    for (int i = 0; i <= N; i++) disArr[i] = INF;

    // 우선순위 큐에 삽입.
    myPQ.push({ 0, S }); // < first : 거리 , second : 노드 인덱스 >
    disArr[S] = 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++) {
            if (check[now][graph[now][i].first] == true) continue;
            // 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));
            }
        }
    }

    return disArr[D];
}


int main()
{
    ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
    //cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
    cin.tie(NULL);
    std::cout.tie(NULL);

    while (true) {

        cin >> N >> M;

        if (N == 0 && M == 0) break;

        cin >> S >> D;

        int result = Dijstra();

        if (result == INF) cout << -1 << "\n";
        else cout << result << "\n";
    }



    return 0;
}

통과된 코드

vector<int> trace[501]; 를 이용하여 시작과 끝의 정점들을 넣어준다.

주의할 점은 도착지에서 출발지 방향으로 탐색을 하기 위해서 반대로 넣어주어야 한다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

constexpr int INF = INT32_MAX;

int disArr[501];

priority_queue<pair<int, int>> mypq;

vector<pair<int, int>> graph[10001];

vector<int> trace[501];

int N, M, S, D, U, V, P;

void MyDijstra()
{  
    for (int i = 0; i <= N; i++) disArr[i] = INF;

    for (int i = 0; i < M; i++) {
        cin >> U >> V >> P;
        graph[U].push_back(make_pair(V, P));
    }

    // 우선순위 큐에 삽입.
    mypq.push({ 0, S }); // < first : 거리 , second : 노드 인덱스 >

    disArr[S] = 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]) {

                if (dissum < disArr[graph[now][i].first]) {
                
                    // 임시 노드 업데이트
                    disArr[graph[now][i].first] = dissum;

                    trace[graph[now][i].first].clear(); // 새로 갱신한다면 전에 있던 것이 필요가 없다.
                    trace[graph[now][i].first].push_back(now); // 경로를 저장

                    // 우선순위 큐에 (거리, 노드 인덱스) 푸시
                    mypq.push(make_pair(-dissum, graph[now][i].first));
                }
                else trace[graph[now][i].first].push_back(now); // 경로를 저장 역방향으로 넣어준다.
            }
        }
    }

    // 최단 거리의 경로를 삭제해 줍니다.
    queue<int> delQ;
    delQ.push(D);
    while (!delQ.empty()) {
        int nowDel = delQ.front();
        delQ.pop();
        for (int i = 0; i < trace[nowDel].size(); i++) {
            for (auto it = graph[trace[nowDel][i]].begin(); it != graph[trace[nowDel][i]].end(); it++) {
                if ((*it).first == nowDel) {
                    delQ.push(trace[nowDel][i]);
                    graph[trace[nowDel][i]].erase(it);
                    break;
                }
            }
        }
    }


    // 새로운 데이크스트라를 진행하여 거의 최단 경로를 찾는다.
    for (int i = 0; i <= N; i++) disArr[i] = INF;
    // 우선순위 큐에 삽입.
    mypq.push({ 0, S }); // first : 거리 , second : 노드 인덱스
    disArr[S] = 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));
            }
        }
    }

    for (int i = 0; i <= N; i++) trace[i].clear();
    for (int i = 0; i <= M; i++) graph[i].clear();
}


int main()
{
    ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
    //cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
    cin.tie(NULL);
    std::cout.tie(NULL);

    while (true) {

        cin >> N >> M;

        if (N == 0 && M == 0) break;

        cin >> S >> D;

        MyDijstra();

        if (disArr[D] == INF) cout << -1 << "\n";
        else cout << disArr[D] << "\n";
    }

    return 0;
}

틀린 코드를 포기할 수 없어 여러가지 방법으로 접근하여 메모리를 줄여보았지만 의미는 없었다.