AVOID 문제 질문입니다

  • kun452
    kun452

    처음에 다이스트라의 변형을 이용해 NUM 배열과 COMPO 벡터의 값을 얻을 수 있는 함수를 구현하였습니다. 그리고나서 COMPO배열을 N번부터 역추적하여 입력된 a의 값의 갯수를 구해서 답을 구했더니 시간초과가 나서 다른방법을 생각하여 처음 1에서부터 N으로 가는 다이스트라중 입려된 a로 가는 방법인 NUM[a]와 그리고 N으로 가는 최단거리의 길들만을 가지고 있는 그래프로 변형한 후 그 그래프를 다시 a부터 N까지 같은 방법으로 다이스트라를 돌려서 NUM[N]에 있는값과 처음 NUM[a]의 값을 곱해서 처음 NUM[N]으로 나누었더니 오답이 뜨네요...

    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <string>
    #include <queue>
    
    using namespace std;
    
    vector <int> compo[101];
    
    void Dijstra(int **A, int N, int start, int *NUM, int *dist, int *visited){
        for(int j=0; j<=N; j++){
            dist[j] = 987654321;
            NUM[j] = 0;
            visited[j] = 0;
        }
    
        compo[start].push_back(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];
                compo[j].push_back(start);
                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]){
                    compo[j].clear();
                    compo[j].push_back(start);
                    dist[j] = dist[start] + A[start][j];    
                    NUM[j] = NUM[start];
                }else if(dist[start] + A[start][j] == dist[j]){
                    compo[j].push_back(start);
                    NUM[j] += NUM[start];
                }else{
                    continue;
                }
            }
        }
    
    }
    
    
    int main(){
        int num;
        cin >> num;
    
        for(int i=0; i<num; i++){
            int N, line, k;
    
            for(int j=0; j<101; j++)
                compo[j].clear();
    
            cin >> N >> line >> k;
    
            int **A = new int*[N+1];
    
            for(int j=0; j<N+1; j++){
                A[j] = new int[N+1];
    
                for(int k=0; k<N+1; 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];
            int *visited = new int[N+1];
    
            Dijstra(A, N, 1, NUM, dist, visited);
    
            // 새로 만든다 ㅋ
    
            int **temp = new int*[N+1];
    
            for(int j=0; j<N+1; j++){
                temp[j] = new int[N+1];
    
                for(int k=0; k<N+1; k++){
                    temp[j][k] = 987654321;
                }
            }
    
            queue <int> q;
            q.push(N);
            int *visited2 = new int[N+1];
    
            for(int j=0; j<=N; j++)
                visited2[j] = 0;
    
            while(!q.empty()){
                int start = q.front();
                visited2[start] = 1;
                q.pop();
    
                int SIZE = compo[start].size();
    
                for(int k=0; k<SIZE; k++){
                    if(!visited2[compo[start][k]])
                        q.push(compo[start][k]);
                    temp[start][compo[start][k]] = 1;
                    temp[compo[start][k]][start] = 1;
                }
            }
    
            for(int j=1; j<=N; j++){
                for(int k=1; k<=N; k++){
                    if(temp[j][k] == 987654321)
                        A[j][k] = 987654321;
                }
            }
    
            for(int j=0; j<k; j++){
                cin >> a;
    
                if(a == N){
                    cout << "1/1" << endl;
                    continue;
                }
    
                // 새로
                long long p = NUM[a];
                int q = NUM[N];
                //cout << "여기 " << p << " " << q << endl;
                Dijstra(A, N, a, NUM, dist, visited);
    
                p *= (long long)NUM[N];
    
    
                if(p == 0){
                    cout << "0/1" << endl;
                }else{
                    if(q / p != 0){ // 나누어 질 때
                        cout << "1/" << q/p << endl;
                    }else{
                        cout << p << "/" << q << endl;
                    }
                }
            }
    
        }
        return 0;
    }
    

    5년 전
5개의 댓글이 있습니다.
  • JongMan
    JongMan

    자세히는 못 봤는데.. 우선 p/q를 약분해서 출력하셔야 하고요. NUM도 32비트 정수형이어서는 범위를 벗어날 수 있습니다.


    5년 전 link
  • kun452
    kun452

    NUM 배열 long long 으로 바꾸고 입력받은 a값이 만약에 N이랑 같은데 NUM[a]가 0일때 0인 조건을 추가했는데도 안되네요;;ㅠ


    5년 전 link
  • nosiar
    nosiar

    4/6 이런건 약분이 안될거 같아요.


    5년 전 link
  • kun452
    kun452

    gcd를 구해서 해봤는데도 안되네요 ㅠㅠ 뭔가 알고리즘에 문제가 있는듯 한데 뭐가 잘못된건지 모르겠네요 ㅠㅠ


    5년 전 link
  • 79brue
    79brue

    자주 하는 실수 모음 도움이 될지도...


    5년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.