UVa 116: Undirectional TSP

简单动态规划题。用取模实现第一行与最后一行连续，注意取字典序即可。

我的解题代码如下：

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

#define min(a,b) ((a<b)?a:b)

#define max(a,b) ((a>b)?a:b)

#define UL(i) ((i+M-1)%M)

#define DL(i) ((i+1)%M)

#define Maxm 12

#define Maxn 105

const int INF = 0x7fffffff;

int M,N;

int Table[Maxm][Maxn];

int MinWeight[Maxm][Maxn], RightRow[Maxm][Maxn];

bool vis[Maxm][Maxn];

int dp(int i, int j)

{

	if(vis[i][j]) return MinWeight[i][j];

	vis[i][j] = true;

	if(j==N-1)	return MinWeight[i][j] = Table[i][j];

	int tmp = min ( dp(UL(i),j+1), min ( dp(i,j+1), dp(DL(i),j+1)));

	RightRow[i][j] = Maxm;

	if(tmp == MinWeight[i][j+1]) RightRow[i][j] = i;

	if(tmp == MinWeight[UL(i)][j+1] && UL(i)<RightRow[i][j]) RightRow[i][j] = UL(i);

	if(tmp == MinWeight[DL(i)][j+1] && DL(i)<RightRow[i][j]) RightRow[i][j] = DL(i);

	return MinWeight[i][j] = tmp+Table[i][j];

}

int main()

{

	while(cin >> M >> N)

	{

		for(int i=0; i<M; i++)

			for(int j=0; j<N; j++)

				cin >> Table[i][j];

		memset(vis,false,sizeof(vis));

		int nMinWeight = INF, iRow;

		for(int i=0; i<M; i++)

		{

			if(nMinWeight > dp(i,0))

			{

				nMinWeight = MinWeight[i][0];

				iRow = i;

			}

		}

		cout << iRow+1;

		for(int j=0; j<N-1; j++) cout << ' ' << (iRow = RightRow[iRow][j])+1;

		cout << endl << nMinWeight << endl;

	}

	return 0;

}

巴特西

UVa 116: Undirectional TSP

最新文章

热门文章