problem:TSP1 TSP1 제출 오류에 대해 문의드립니다.

  • jwl1993
    jwl1993

    예제 input으로는 답이 나오는데 제출을 하면 오답이 나오네요..
    고민을 많이 해봤는데.. 제눈에는 잘 안보여서 이렇게 질문 드립니다.

    #include <iostream>
using namespace std;

double **cost;
double sum;
bool *visited;
double *weight;
int n;
void FindPath(int start);

int main(){
    int Case;
    cin >> Case;
    while(Case--){
        cin >> n;
        cout.precision(10);
        visited = new bool[n];
        weight = new double[n];
        cost = new double*[n];
        for(int i = 0; i< n; i++)
            cost[i] = new double[n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++)
                cin >> cost[i][j]; 
        }

        for(int i = 0 ; i < n ; i++){
            for(int j = 0; j < n; j++){
                visited[j] = false;
                weight[j] = -1;
            }
            weight[i] = 0;
            FindPath(i);
        }
        cout<<fixed<<sum<<endl;
    }
    return 0;
}

void FindPath(int start){
    visited[start] = true;
    for(int i = 0; i < n; i++ ){
        if(!visited[i] && cost[start][i] != 0 && i != start){
            if(weight[i] == -1){
                weight[i] = cost[start][i] + weight[start];
            }
            else{
                if(weight[i] > cost[start][i] + weight[start])
                    weight[i] = cost[start][i] + weight[start];
            }
            FindPath(i);
        }
    } // 최단 경로 구하기  

    int check = 0; //경로 구한 것 골라내기 
    for(int j = 0; j < n; j++){
        if(visited[j] == false)
            check++;
    }
    if(check == 0){
        double max = weight[0];
        for(int i = 0; i < n; i++){
            if(max < weight[i])
                max = weight[i];
        }
        if(max < sum && sum != 0)
            sum = max;
        else if(sum == 0)
            sum = max;
        return;
    }
}

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

    sum은 어디서 초기화하시나요


    8년 전 link
  • jwl1993
    jwl1993

    Case 로 들어가기 전에 sum을 초기화하겠습니다. 그런데 그것이 문제가 되는 case도 있나요?


    8년 전 link
  • jwl1993
    jwl1993

    while문안에서 sum을 초기화 하였습니다. 그런데 계속 오류가 나는 거 같습니다. 음.. 알고리즘쪽에 문제가 있는게 아닐까요?


    8년 전 link
  • jwl1993
    jwl1993

    아래와 같이 바꿔보았는데도 오류가 나는거같네요.. 알고리즘에 문제가 있는거 같은데 조언을 해주실수 있을까요

    #include <iostream>
using namespace std;

double **cost;
double sum;
bool *visited;
double *weight;
int n;
bool FindPath(int start, int count);

int main(){
    int Case;
    cin >> Case;
    while(Case--){
        cin >> n;
        sum = 0;
        cout.precision(10);
        visited = new bool[n];
        weight = new double[n];
        cost = new double*[n];
        for(int i = 0; i< n; i++)
            cost[i] = new double[n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++)
                cin >> cost[i][j]; 
        }

        for(int i = 0 ; i < n ; i++){
            for(int j = 0; j < n; j++){
                visited[j] = false;
                weight[j] = -1;

            }
            weight[i] = 0;
            FindPath(i, 1);
        }
        cout<<fixed<<sum<<endl;
    }
    return 0;
}

bool FindPath(int start, int count){
    if(count == n){
            if(sum != 0){
                if(sum > weight[start])
                    sum = weight[start];
            }
            else
                sum = weight[start];
            return true;
    }
    visited[start] = true;
    for(int i = 0; i < n; i++ ){
        if(!visited[i]){
            if(weight[i] == -1){
                weight[i] = cost[start][i] + weight[start];
            }
            else{
                if(weight[i] > cost[start][i] + weight[start])
                    weight[i] = cost[start][i] + weight[start];
            }

            FindPath(i, count +1);
        }
    } // 최단 경로 구하기  
}

    8년 전 link
  • JongMan
    JongMan

    모든 경로를 탐색하지 않고 계시네요. 방문하고 있는 경로들을 다 출력해 보세요.


    8년 전 link
  • jwl1993
    jwl1993

    네 그런거 같습니다. 한번 visited가 true 가 된 후에 다시 다른 경로 탐색할때 false로 다시 바꿔야 하는데 그부분이 안되고 있네요. ㅠㅠ


    8년 전 link

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