UVa Problem 116 Unidirectional TSP (단 방향 여행사 문제)

// Unidirectional TSP （       ）
// PC/UVa IDs: 111104/116, Popularity: A, Success rate: low Level: 3
// Verdict: Accepted
// Submission Date: 2011-10-12
// UVa Run Time: 0.252s
//
//     （C）2011，  。metaphysis # yeah dot net
//
// [   PDF       ]
// http://uva.onlinejudge.org/external/1/116.pdf
//
// [    ]
//              、   、         ，               ，   
//                ，      （           ）：
//
// matrix[i][j] += min{matrix[i][j - 1]，matrix[i - 1][j - 1]，matrix[i + 1][j - 1]}
//
//     DP，                  ，            ，          
//   ，                。  ：                   ，    
//      DP，                 ，                  ，    ：
//
// 3 4 1 2 8 6
// 1 2 8 2 1 1
// 5 9 3 9 9 5
// 1 1 1 3 1 1
// 3 7 2 8 6 4
//
//                ，             ，           2 - 2 - 1 -
// 1 - 2 - 2，           DP，             ，              
//  。               ，           30    ，        100  ，  
//       long long    。

#include <iostream>

using namespace std;

#define MAXLINE 11
#define MAXROW 101
#define MAXINT (1 << 30 - 1)

int main(int ac, char *av[])
{
	int line, row, tag, tmp;
	int successor[MAXLINE][MAXROW];
	long long matrix[MAXLINE][MAXROW];
	long long min;
	
	while (cin >> line >> row)
	{
		for (int i = 1; i <= line; i++)
			for (int j = 1; j <= row; j++)
				cin >> matrix[i][j];

		//      ，          ，                ，    
		//     ，             ，            。
		for (int j = row - 1; j >= 1; j--)
		{
			for (int i = 1; i <= line; i++)
			{
				min = MAXINT;

				tmp = (i == 1 ? line : i - 1);
				if (min > matrix[tmp][j + 1])
				{
					min = matrix[tmp][j + 1];
					tag = tmp;
				}
				else if (min == matrix[tmp][j + 1] && tag > tmp)
					tag = tmp;

				if (min > matrix[i][j + 1])
				{
					min = matrix[i][j + 1];
					tag = i;
				}
				else if (min == matrix[i][j + 1] && tag > i)
					tag = i;

				tmp = (i == line ? 1 : i + 1);
				if (min > matrix[tmp][j + 1])
				{
					min = matrix[tmp][j + 1];
					tag = tmp;
				}
				else if (min == matrix[tmp][j + 1] && tag > tmp)
					tag = tmp;

				matrix[i][j] += min;
				successor[i][j] = tag;
			}
		}

		//          。
		min = MAXINT;
		for (int i = 1; i <= line; i++)
			if (matrix[i][1] < min)
			{
				min = matrix[i][1];
				tag = i;
			}

		//   。
		cout << tag;
		int next = 1;
		int tmp = tag;
		while (next < row)
		{
			cout << " " << successor[tmp][next];
			tmp = successor[tmp][next];
			next++;
		}

		cout << endl;
		cout << matrix[tag][1] << endl;
	}

	return 0;
}