글 읽기 - TSP문제 완전탐색

jjongbumee 5년 전 1

TSP 문제를 완전탐색 이용해서 풀어보려고하는데, 안되네요.

문제의 예제, 그외의 테스트케이스들을 테스트해도 잘 나오는데 어디가 문제인지 잘 모르겠습니다.

<테스트해본 입력>

4
0 1 0 9
9 0 1 0
0 9 0 1
0 0 9 0

3
0 1 0
0 0 1
1 0 0

혹시 문제점을 아시거나, 반례를 찾으신 분은 알려주시면 감사하겠습니다.

#include <bits/stdc++.h>
#define INF 1000001
using namespace std;
int N, tmp;
//각 도시간 이동하는데 드는 비용
int costs[10][10];

//인자 : 방문여부, 현재까지 든 비용, 이전 위치(도시), 이동한 도시 수, 시작한 도시
int shortest(vector<bool>& visited, int cost, int prev, int size, int first) { 
	if(size == N) return min(INF, cost+costs[prev][first]);
	int ret = INF;
	for(int i = 0; i < N; i++) {
		if(visited[i]) continue;
		visited[i] = true;
		ret = min(shortest(visited, cost+costs[prev][i], i, size+1, first), ret);
		visited[i] = false;
	}
	return ret;
}

int main() {
	int cmp = INF;
	cin.sync_with_stdio(false);
	cin >> N;
	vector<bool> visited(N, false);
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {
			cin >> tmp;
			if(tmp == 0){
				costs[i][j] = INF;
			}
			else {
				costs[i][j] = tmp;
			}
		}
	}
    //시작 도시 정하기
	for (int i = 0; i < N; i++) {
		visited[i] = true;
		cmp = min(cmp, shortest(visited, 0, i, 1, i));
		visited[i] = false;
	}
	cout << cmp;
}

djm03178 5년 전 1

INF가 너무 작습니다.

https://ideone.com/XbEWgX

jjongbumee 5년 전 0

드디어 해결했네요. 감사합니다!!

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

문제

문제

출처

ICPC

TSP문제 완전탐색

jjongbumee 5년 전 1

djm03178 5년 전 1

jjongbumee 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말