알고스팟_여행하는 외판원

https://www.algospot.com/judge/problem/read/TSP1

algospot.com :: TSP1

 풀이방법

 첫번째 풀이

 

 처음에 크루스칼 알고리즘으로도 풀수있는지알고 시도해봤는데.. 생각해보니 이 문제는 1자경로여야만 하므로 최소신장트리를 구하는 방법으로는 구할수 없다. ㅋㅋㅋㅋ

 

 두번째 풀이

 

 시간이 1초 (약 1억) 이므로 완전탐색 : 테스트케이스( 50 ) X (최대도시수 8)! = 2,016,000 이므로 완전탐색 방법으로도 충분히 가능하다는 계산이 나온다. 그러니 완전탐색으로 풀자. 밑의 코드는 종만북을 보고했다.

---

전체코드 

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <iomanip>
#define MAX_VALUE 987654321.
using namespace std;

int n;
double dist[10][10];

double getShortDist(vector<int>& path, vector<bool>& visited, double length)
{
	//탈출조건
	if (path.size() == n)
	{
		return length;
	}

	double ret = MAX_VALUE;

	//다음 갈곳 찾기
	for (int next = 0; next < n; next++)
	{
		if (visited[next] == true)
			continue;
		int here = path.back();
		path.push_back(next);
		visited[next] = true;
		ret = min(ret, getShortDist(path, visited, length + dist[here][next]));
		path.pop_back();
		visited[next] = false;
	}
	return ret;
}

int main()
{
	int c;
	cin >> c;
	for (int i = 0; i < c; i++)
	{
		cin >> n;
		double value;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				cin >> value;
				dist[i][j] = value;
			}
		}

		//get value
		vector<int> path;
		vector<bool> visited;
		visited.resize(n, false);
		double ans = MAX_VALUE;
		for (int i = 0; i < n; i++)
		{
			path.push_back(i);
			visited[i] = true;
			ans = min(ans, getShortDist(path, visited, 0.));
			path.pop_back();
			visited[i] = false;
		}
		cout <<fixed << setprecision(10)<< ans << endl;
	}
	return 0;
}

---

 후기

 일자경로라는것을 보지 않고 최소신장트리 알고리즘을 이용하면 더 시간을 줄일수있을거 같아 썼다가 그냥 시간만 날렸다. ㅠㅠ