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;
        }
    }
    

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

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


    3년 전 link
  • jwl1993
    jwl1993

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


    3년 전 link
  • jwl1993
    jwl1993

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


    3년 전 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);
            }
        } // 최단 경로 구하기  
    }
    

    3년 전 link
  • JongMan
    JongMan

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


    3년 전 link
  • jwl1993
    jwl1993

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


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