UVA - 116 Unidirectional TSP 多段图的最短路

题目大意：给出一个矩阵，要求每列都要路过，起点必须是第一列，求经过的最短路径的上面的数字和最小

解题思路：公式为d[i][j] = min(d[i][j+1],d[i+1][j+1],d[i-1][j+1]) + a[i][j]，本题要注意，因为可以从最上面一行到最后一行，或者从最后一行到第一行，注意i的变化

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 300 + 10;
int row,col;
int DP[maxn][maxn];
int m[maxn][maxn];
int ans[maxn][maxn];

int main() {
	while(scanf("%d%d",&row,&col) != EOF) {
		for(int i = 1; i <= row; i++)
			for(int j = 1; j <= col; j++) 
				scanf("%d", &m[i][j]);	

		memset(ans,0,sizeof(ans));
		int min_ = 0x3f3f3f3f;	
		int first;
		for(int i = col; i >= 1; i--)  {
			for(int j = 1; j <= row; j++) {
				if(i == col)	
					DP[j][i] = m[j][i];
				else{
					int mov[3] = {j,j-1,j+1};
					if(j == row)
						mov[2] = 1;
					if(j == 1)
						mov[1] = row;	
					sort(mov,mov+3);
					DP[j][i] = 0x3f3f3f3f;
					for(int k = 0; k < 3; k++) {
						int temp = DP[mov[k]][i+1] + m[j][i];
						if(temp < DP[j][i]) {
							DP[j][i] = temp;
							ans[j][i] = mov[k];
						}
					}
				}
				if(i == 1 && DP[j][i] < min_) {
					min_ = DP[j][i];
					first = j;
				}
			}
		}
		printf("%d",first);
		int i,j;
		for(i = ans[first][1],j = 2; j <= col;i = ans[i][j],j++)
			printf(" %d",i);
		printf("\n");
		printf("%d\n",min_);
	}
	return 0;
}