UVa 116 单向TSP（多段图最短路）

https://cn.vjudge.net/problem/UVA-116

题意：给出m行n列的整数矩阵，从第一列任何一个位置出发每次往右，右上或右下走一格，最终到达最后一列，要求经过的整数之和最小。

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int INF = 0x7FFFFFFF;

 const int maxn =  + ;

 int m, n;

 int a[maxn][maxn];

 int dp[maxn][maxn];

 int next[maxn][maxn];

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     while (cin >> m >> n && m && n)

     {

         for (int i = ; i < m;i++)

         for (int j = ; j < n; j++)

             cin >> a[i][j];

         int first = ;

         int ans = INF;

         for (int j = n - ; j >= ; j--)

         {

             for (int i = ; i < m; i++)

             {

                 if (j == n - )  dp[i][j] = a[i][j];  //边界

                 else

                 {

                     dp[i][j] = INF;

                     int row[] = { i, i + , i -  };

                     if (i == )       row[] = m - ;

                     if (i == m - )   row[] = ;

                     sort(row, row + );   //重新排序，以便找到字典序最小的

                     for (int k = ; k < ; k++)

                     {

                         int v = dp[row[k]][j + ] + a[i][j];

                         if (v < dp[i][j])      { dp[i][j] = v; ::next[i][j] = row[k];}

                     }

                 }

                 if (j ==  && dp[i][j] < ans)  {

                     ans = dp[i][j]; first = i;

                 }

             }

         }

         cout << first + ;

         for (int i = ::next[first][], j = ; j < n; i = ::next[i][j], j++)

             cout << " " << i + ;

         cout << endl << ans << endl;

     }

     return ;

 }