TSP1 처리 못한 케이스가 무엇인지 궁금합니다.

  • dalkomsft02
    dalkomsft02
    **  재귀를 통해  정점에서 방문하지 않은 정점  최소 길이인 값을 더해가고  거리들을 반환하여 최단거리를 구합니다.
    모든 정점에 대해서   방법을 사용합니다. **
    
    
    using namespace std;
    
    void loadCost();
    double minDistClac(const vector<vector<double> >& dist, vector<bool> visit, double curDist, const int& cnt, int v);
    
    
    double minDistClac(const vector<vector<double> >& dist, vector<bool> visit, double curDist, const int& cnt, int v)
    {
        visit[v] = true;
        double minDist = ~(1<<31);
        int minV = 0;
        for(int i = 0; i < cnt; i++)
        {
            if(!visit[i] && minDist >= dist[v][i])
            {
                minDist = dist[v][i];
                minV = i;
            }
        }
    
        if(minDist == ~(1<<31)) return curDist;
        else return curDist + minDistClac(dist, visit, minDist, cnt, minV);
    }
    
    
    void loadCost()
    {
    
        int n;
        scanf("%d", &n);
    
        vector<vector<double>> dist(n);
        vector<bool> visit(n, false);
    
        for(auto &e : dist)
        {
            for(int i = 0; i < n; i++)
            {
                double cost;
                cin >> cost;
                e.push_back(cost);
            }
        }
    
        double minDist = ~(1<<31);
    
        for(int i = 0; i < n; i++)
        {
            minDist = min(minDist, minDistClac(dist, visit, 0.0, n, i));
        }
    
        printf("%.10f\n", minDist);
    
    }
    
    int main()
    {
        int c;
        cin >> c;
        while(c--)
        {
            loadCost();
        }
    
        return 0;
    }
    

    8년 전
3개의 댓글이 있습니다.
  • dalkomsft02
    dalkomsft02

    그리디하게 풀어서 틀린 것인가요


    8년 전 link
  • JongMan
    JongMan

    네.


    8년 전 link
  • dalkomsft02
    dalkomsft02

    감사합니다. 재귀부분을 이렇게 고쳐서 해결하였습니다.

    ~~ c++
    double minDistClac(const vector >& dist, vector visit, double curDist, const int& cnt, int v)
    {
    visit[v] = true;
    double minDist = ~(1<<31);

    for(int i = 0; i < cnt; i++)
    {
        if(!visit[i])
        {
            minDist = min(minDist, curDist + minDistClac(dist, visit, dist[v][i], cnt, i));
        }
    }
    
    if(minDist == ~(1<<31)) return curDist;
    else return minDist;

    }


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