안녕하세요 NEWBUS를 풀었는데 계속 오답이 떠서 질문드립니다
최단거리를 구하기 위해 다이스트라 알고리즘을 사용하였는데요 여기서 dist배열의 값을 갱신시켜줄 때 방문했던거와 관련없이 현제 start에서의 값이 더 작다면 dist배열을 바꿔주고 같으면 NUM배열을 하나 증가 크면 넘어가도록 하였는데 뭐가 잘못됬는지 잘 모르겠네요...

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

void Dijstra(int **A, int N, int start, int *NUM, int *dist){
    int *visited = new int[N+1];
    
    for(int j=0; j<=N; j++){
        dist[j] = 987654321;
        NUM[j] = 0;
        visited[j] = 0;
    }

    dist[start] = 0;
    NUM[start] = 0;
    visited[start] = 1;
    for(int j=1; j<=N; j++){
        if(A[start][j] != 987654321){
            dist[j] = A[start][j];
            NUM[j]++;
        }
    }

    int num = 1;

    while(num < N){
        num++;
        int MIN = 987654322;
        int min_index;

        for(int j=1; j<=N; j++){
            if(!visited[j] && dist[j] < MIN){
                MIN = dist[j];
                min_index = j;
            }
        }

        start = min_index;
        visited[start] = 1;

        for(int j=1; j<=N; j++){
            if(dist[start] + A[start][j] < dist[j]){
                dist[j] = dist[start] + A[start][j];
                NUM[j] = 1;
            }else if(dist[start] + A[start][j] == dist[j]){
                NUM[j] ++;
            }else{
                continue;
            }
        }
    }

}   

int main(){
    int num;
    cin >> num;

    for(int i=0; i<num; i++){
        int N, line, Q;
        cin >> N >> line >> Q;

        int **A = new int*[N+1];

        for(int j=0; j<=N; j++){
            A[j] = new int[N+1];

            for(int k=0; k<=N; k++){
                A[j][k] = 987654321;
            }
        }

        int a, b, w;

        for(int j=0; j<line; j++){
            cin >> a >> b >> w;
            A[a][b] = w;
            A[b][a] = w;
        }

        int *NUM = new int[N+1];
        int *dist = new int[N+1];

        for(int j=0; j<Q; j++){
            cin >> a >> b;

            Dijstra(A, N, a, NUM, dist);
            
            if(NUM[b] == 0)
                cout << "no" << endl;
            if(NUM[b] == 1)
                cout << "only" << endl;
            if(NUM[b] >= 2)
                cout << "many" << endl;
            //cout << NUM[b] << endl;

        }
    }

    return 0;
}