UVa 116 Unidirectional TSP

簡化版旅行推銷員問題，用DP解

這題我的醒悟就是，用演算法不要太死腦筋
因為這題有一個機歪點，就是如果有多條權重相同的最短路徑，要輸出字典順序最小的那一條。

如果從起點往後DP，那麼字典順序很難解
如果從終點DP回來起點，那麼字典順序自然而然解決了。

瞭解演算法以後，果然還是要靈活使用才行。


附上測資
應該足夠應付各種狀況了

	/**
	* UVa 116 (AC)
	* Author: chchwy
	* Last Modified: 2009.04.28
	*/
	#include<iostream>
	enum { MAX_ROW = 15, MAX_COL = 100 };
	int getInt()
	{
	int i = 0, sign = 1;
	char c = getchar();
	while (c == ' ' || c == '\n' || c == '\r')
	c = getchar();
	if (c == '-')
	{
	sign = -1;
	c = getchar();
	}
	while (c > '0' - 1 && c < '9' + 1)
	{
	i = i * 10 + (c - '0');
	c = getchar();
	}
	return i * sign;
	}
	void readMap(int map[][MAX_COL], int row, int col)
	{
	for (int i = 0; i < row; ++i)
	for (int j = 0; j < col; ++j)
	map[i][j] = getInt();
	}
	int main()
	{
	#ifndef ONLINE_JUDGE
	freopen("116.in", "r", stdin);
	#endif
	int row, col;
	int map[MAX_ROW][MAX_COL];
	while (scanf("%d %d ", &row, &col) == 2)
	{
	readMap(map, row, col);
	int path[MAX_ROW][MAX_COL]; //record the min path weight
	int next[MAX_ROW][MAX_COL]; //record the next path
	for (int i = 0; i < MAX_ROW; ++i)
	{
	path[i][col - 1] = map[i][col - 1];
	next[i][col - 1] = -1;
	}
	//DP shortest path
	for (int j = col - 2; j > -1; --j)
	{
	for (int i = 0; i < row; ++i)
	{
	int a = (i + row - 1) % row;
	int b = i;
	int c = (i + 1) % row;
	int min = a;
	if ( path[b][j + 1] < path[min][j + 1])
	min = b;
	else if (path[b][j + 1] == path[min][j + 1] && b < min)
	min = b;
	if ( path[c][j + 1] < path[min][j + 1])
	min = c;
	else if (path[c][j + 1] == path[min][j + 1] && c < min)
	min = c;
	path[i][j] = map[i][j] + path[min][j + 1];
	next[i][j] = min;
	}
	}
	//terminal place
	int min = 0;
	for (int i = 1; i < row; ++i)
	if (path[i][0] < path[min][0])
	min = i;
	int minCost = path[min][0];
	for (int i = 0; i < col - 1; ++i)
	{
	printf("%d ", min + 1);
	min = next[min][i];
	}
	printf("%d", min + 1);
	printf("\n%d\n", minCost);
	}
	return 0;
	}

view raw 116.cpp hosted with ❤ by GitHub