UVA 116 Unidirectional TSP——dp

简单递推

#include #include #include #include using namespace std;const int maxn = 110;const int INF = 0x3f3f3f3f;int m, n, a[maxn][maxn], dp[maxn][maxn], path[maxn][maxn];int main() { while (~scanf("%d %d", &m, &n)) { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { scanf("%d", &a[i][j]); } } for (int i = 0; i < m; i++) dp[i][n-1] = a[i][n-1]; for (int j = n-2; j >= 0; j--) { for (int i = 0; i < m; i++) { int t1 = (i-1+m)%m, t2 = (i+1)%m; dp[i][j] = min(dp[i][j+1],min(dp[t1][j+1], dp[t2][j+1]))+a[i][j]; int t[] = {t1, i, t2}; sort(t, t+3); for (int k = 0; k < 3; k++) { if (dp[i][j] == dp[t[k]][j+1]+a[i][j]) { path[i][j] = t[k]; break; } } } } int ans = INF, pos = 0; for (int i = 0; i < m; i++) { if (dp[i][0] < ans) { ans = dp[i][0]; pos = i; } } for (int j = 0; j < n; j++) { if (j) printf(" "); printf("%d", pos+1); pos = path[pos][j]; } printf("\n%d\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。