程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu3001——Travelling 三進制TSP, 狀態壓縮

hdu3001——Travelling 三進制TSP, 狀態壓縮

編輯：C++入門知識

hdu3001——Travelling 三進制TSP, 狀態壓縮

Travelling

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4106 Accepted Submission(s): 1310

Problem Description After coding so many days,Mr Acmer wants to have a good rest.So travelling is the best choice!He has decided to visit n cities(he insists on seeing all the cities!And he does not mind which city being his start station because superman can bring him to any city at first but only once.), and of course there are m roads here,following a fee as usual.But Mr Acmer gets bored so easily that he doesn't want to visit a city more than twice!And he is so mean that he wants to minimize the total fee!He is lazy you see.So he turns to you for help.
Input There are several test cases,the first line is two intergers n(1<=n<=10) and m,which means he needs to visit n cities and there are m roads he can choose,then m lines follow,each line will include three intergers a,b and c(1<=a,b<=n),means there is a road between a and b and the cost is of course c.Input to the End Of File.
Output Output the minimum fee that he should pay,or -1 if he can't find such a route.
Sample Input

Sample Output

100
90
7

Source 2009 Multi-University Training Contest 11 - Host by HRBEU
Recommend gaojie | We have carefully selected several similar problems for you: 3004 3002 3006 3007 3003

這題一看就是TSP，然後想到要狀壓，但是這裡每個城市最多可以走兩次，所以不能用普通的二進制來狀壓，需要三進制

三進制每一位是0 1 2， 0表示這座城市沒到過，1表示到過一次，2表示到過兩次
由於一共10座城市，我們先把3^0 --- 3 ^ 10預處理出來，然後化作三進制存好，接著就是dp，但是要注意，可以作為最後狀態的狀態，它的每一位都不為0（否則就有某個城市沒到過），最後枚舉所有可以作為尾狀態的狀態然後求個最小值就ok了

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

const int inf = 0x3f3f3f3f;

int dp[60000][15];
int dist[15][15];
int three[15] = {0, 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049};
int city[60000][15];

int main()
{
	int n, m, u, v, w;
	memset (city, inf, sizeof(city));
	for (int i = 0; i < 59059; ++i)
	{
		int tmp = i;
		for (int j = 1; j <= 10; ++j)
		{
			city[i][j] = tmp % 3;
			tmp /= 3;
		}
	}
	while (~scanf("%d%d", &n, &m))
	{
		memset (dist, inf, sizeof(dist));
		memset (dp, inf, sizeof(dp));
		for (int i = 1; i <= n; ++i)
		{
			dp[three[i]][i] = 0;
		}
		dp[0][0] = 0;
		for (int i = 1; i <= m; ++i)
		{
			scanf("%d%d%d", &u, &v, &w);
			dist[u][v] = min(dist[u][v], w);
			dist[v][u] = dist[u][v];
		}
		int ans = inf;
		for (int i = 0; i < three[n + 1]; ++i)
		{
			bool is_end = 1;
			for (int j = 1; j <= n; ++j)
			{
				if (city[i][j] == 0)
				{
					is_end = 0;
				}
				for (int k = 1; k <= 10; ++k)
				{
					if (city[i][j] == 2)
					{
						continue;
					}
					dp[i + three[j]][j] = min(dp[i + three[j]][j], dp[i][k] + dist[k][j]);
				}
			}
			if (is_end)
			{
				for (int j = 1; j <= n; ++j)
				{
					ans = min(ans, dp[i][j]);
				}
			}
		}
		if (ans == inf)
		{
			printf("-1\n");
			continue;
		}
		printf("%d\n", ans);
	}
	return 0;
}