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;
}