利用DP去紀錄一層一層每一列的最短路徑該往哪走即可得解。
C++(0.135)
/*******************************************************/ /* UVa 116 Unidirectional TSP */ /* Author: LanyiKnight [at] knightzone.studio */ /* Version: 2014/09/30 */ /*******************************************************/ #include <iostream> #include <cstdio> #include <climits> using namespace std; int main(){ int m, n; while( scanf("%d%d", &m, &n) != EOF ){ int weight[105][105] = {0}, dp[105][105] = {0}, path[105][105] = {0}; for( int i = 0 ; i < m ; ++i ){ for( int j = 0 ; j < n ; ++j ){ scanf("%d", &weight[i][j]); dp[i][j] = weight[i][j]; } } for( int j = n-2 ; j >= 0 ; --j ){ for( int i = 0 ; i < m ; ++i ){ int up, middle, down; up = weight[i][j] + dp[(i-1+m)%m][j+1]; middle = weight[i][j] + dp[i][j+1]; down = weight[i][j] + dp[(i+1)%m][j+1]; path[i][j] = INT_MAX; if( up <= middle && up <= down ){ dp[i][j] = up; path[i][j] = min( path[i][j], (i-1+m)%m ); } if( middle <= up && middle <= down ){ dp[i][j] = middle; path[i][j] = min( path[i][j], i ); } if( down <= up && down <= middle ){ dp[i][j] = down; path[i][j] = min( path[i][j], (i+1)%m ); } } } int minPath = INT_MAX, mini = -1; for( int i = 0 ; i < m ; ++i ){ if( dp[i][0] < minPath ){ minPath = dp[i][0]; mini = i; } } int next = mini; printf("%d", mini+1); for( int i = 0 ; i < n-1 ; ++i ){ printf(" %d", path[next][i]+1); next = path[next][i]; } printf("\n%d\n", dp[mini][0]); } return 0; }
回應