글 읽기 - 10971번 외판원 순회 2 시작점에 따라 답이 달라요...(완탐)

hahawjstk 5년 전 0

0 base로 해서 비용 W배열을 받았습니다.

원래 tsp문제는 어디서 시작하든 사이클이 존재해서 답이 똑같이 나와야되는데

시작에 따라서 답이 달라져요.....

어떤 것이 문제인가요....?ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

//  https://www.acmicpc.net/problem/10971
//  10971_외판원 순회 2.cpp
//  summer_week1-2
//
//  Created by Hoon on 2018. 8. 21..
//  Copyright © 2018년 Hoon. All rights reserved.
//

#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAXX 987654321


int N,W[14][14];
bool visited[14];
int ans = MAXX;

void tsp(int node , int nowSum , int count){
    if(count == N) {
        if(W[node][0] != 0) //시작점으로 가는 길이 있다면
            ans = min(ans,nowSum+W[node][0]);
        return;
    }
    
    visited[node] = true;
    for (int i = 0; i < N; i++) {
        if(visited[i] == false && W[node][i] != 0){
            if(nowSum + W[node][i] < ans){
                tsp(i , nowSum + W[node][i] , count+1);
            }
        }
    }
    visited[node] = false;
}

int main(){
    scanf("%d" , &N);
    for (int i = 0 ; i < N; i++) {
        for (int j = 0; j < N; j++) {
            scanf("%d" , &W[i][j]);
        }
    }
    
    tsp(0,0,1);
    //(1,0,1) (2,0,1) (3,0,1) 모두 값이 다르다....
    printf("%d" , ans);
}

Green55 5년 전 1

if(W[node][0] != 0)

ans = min(ans,nowSum+W[node][0]);

부분을 안 바꾸셔서 그런 것 같습니다

hahawjstk 5년 전 0

ssangba55

소름 돋았습니다... 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

10971번 외판원 순회 2 시작점에 따라 답이 달라요...(완탐)

hahawjstk 5년 전 0

Green55 5년 전 1

hahawjstk 5년 전 0

ssangba55

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말