algospot.com :: 질문과 답변: AVOID 문제 질문입니다

AVOID 문제 질문입니다

처음에 다이스트라의 변형을 이용해 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;
}

9년 전

5개의 댓글이 있습니다.

JongMan

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

9년 전 link
kun452

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

9년 전 link
nosiar

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

9년 전 link
kun452

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

9년 전 link
79brue

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

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

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

9년 전 link

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

9년 전 link

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

9년 전 link

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

9년 전 link

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

9년 전 link

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

SINCE 2007

다가오는 이벤트들

AVOID 문제 질문입니다

5개의 댓글이 있습니다.