Uva 116，单向TSP

题目链接：https://uva.onlinejudge.org/external/1/116.pdf

和矩形嵌套，巴比伦塔差不多。

题意：

给出矩阵，这个矩阵是环形的，就是说第一行的上一行是最后一行，最后一行的下一行是第一行，要求从最左边一列走到最右边一列，路径上的和最小。多组解输出字典序最小的解。

 

分析：

DAG多段图，dp(i,j)从第i行，第j列出发的最优解，然后走一遍每一行的第一列。

这里的字典序最小，每次决策时的三个选择，每一行，重新排个序，这样就保证了字典序最小。

 

姜来是老的辣，写了好久不知道WA在哪里，快写炸了。然后还是参考了下刘汝佳的写法，确实比我写的好一点，借鉴一下。

 

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f


int a[105][105];
int dp[105][105];
int path[105][105];

int main()
{
    //freopen("in.txt","r",stdin);
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
                scanf("%d",&a[i][j]);
            }
        }

        memset(dp,INF,sizeof(dp));

        int ans = INF+1;
        for(int j=n-1; j>=0; j--)
        {
            for(int i=0; i<m; i++)
            {
                if(j==n-1) dp[i][j] = a[i][j];
                else
                {
                    int row[3] = {i,i-1,i+1};
                    if(i==0) row[1] = m-1;
                    if(i==m-1) row[2] = 0;
                    sort(row,row+3);

                    for(int k=0; k<3; k++)
                    {
                        int v = dp[row[k]][j+1] + a[i][j];
                        if(v<dp[i][j])
                        {
                            dp[i][j] = v;
                            path[i][j] = row[k];
                        }
                    }

                }


            }
        }

        int flag;
        for(int i=0;i<m;i++) {
            if(ans>dp[i][0])
            {
                ans = dp[i][0];
                flag = i;
            }
        }

        printf("%d",flag+1);
        for(int j=1;j<n;j++) {
            printf(" %d",path[flag][j]+1);
            flag = path[flag][j];
        }
        puts("");
        printf("%d
",ans);



    }



    return 0;
}

/*
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define INF 0x3f3f3f3f

int a[15][105];
int dp[15][105];
int path[15][105];
int m,n;

int main()
{
    //freopen("in.txt","r",stdin);

    while(scanf("%d%d",&m,&n)==2&&m) {

        for(int i=1;i<=m;i++) {
            for(int j=1;j<=n;j++)
                scanf("%d",&a[i][j]);
        }

        for(int i=1;i<=m;i++) {
            for(int j=1;j<=n;j++)
                dp[i][j] = INF;
        }

        memset(path,0,sizeof(path));

        for(int i=n;i>=1;i--) {
            for(int j=1;j<=m;j++) {
                if(i==n) {
                    dp[j][i] = a[j][i];
                    path[j][i] = j;
                }
                else {
                    if(j==1) {

                        int temp = INF;
                        int f;

                        if(temp>dp[j][i+1]) {
                            temp = dp[j][i+1];
                            f = j;
                        }
                        if(temp>dp[j+1][i+1]) {
                            temp = dp[j+1][i+1];
                            f = j+1;
                        }
                        if(temp>dp[m][i+1]) {
                            temp = dp[m][i+1];
                            f = m;
                        }

                        dp[j][i] = a[j][i] + temp;
                        path[j][i] = f;

                    }
                    else if(j==m) {

                        int temp = INF;
                        int f;
                        if(temp>dp[1][i+1]) {
                            temp = dp[1][i+1];
                            f = 1;
                        }
                        if(temp>dp[j-1][i+1]) {
                            temp = dp[j-1][i+1];
                            f = j-1;
                        }
                        if(temp>dp[j][i+1]) {
                            temp = dp[j][i+1];
                            f = j;
                        }



                        dp[j][i] = a[j][i] + temp;
                        path[j][i] = f;

                    }
                    else {
                        int temp = INF;
                        int f;
                        if(temp>dp[j-1][i+1])
                        {
                            temp = dp[j-1][i+1];
                            f = j-1;
                        }
                        if(temp>dp[j][i+1]) {
                            temp = dp[j][i+1];
                            f = j;
                        }
                        if(temp>dp[j+1][i+1]) {
                            temp = dp[j+1][i+1];
                            f = j+1;
                        }


                        dp[j][i] = a[j][i]+temp;
                        path[j][i] = f;
                    }

                }
            }
        }

        int flag = 0;
        int ans = INF+1;
        for(int i=1;i<=m;i++) {
            if(ans>dp[i][1])
            {
                flag = i;
                ans = dp[i][1];
            }
        }

        printf("%d",flag);

        for(int i=2;i<=n;i++) {
            printf(" %d",path[flag][i-1]);
            flag = path[flag][i-1];
        }
        puts("");
        printf("%d
",ans);

    }

    return 0;
}
*/

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f


int a[105][105];
int dp[105][105];
int path[105][105];

int main()
{
    freopen("in.txt","r",stdin);
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        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++)
        {
            for(int j=0; j<n; j++)
                dp[i][j] = INF;
        }

        int ans = INF+1;
        for(int j=n-1; j>=0; j--)
        {
            for(int i=0; i<m; i++)
            {
                if(j==n-1) dp[i][j] = a[i][j];
                else
                {
                    int row[3] = {i,i-1,i+1};
                    if(i==0) row[1] = m-1;
                    if(i==m-1) row[2] = 0;
                    sort(row,row+3);

                    for(int k=0; k<3; k++)
                    {
                        int v = dp[row[k]][j+1] + a[i][j];
                        if(v<dp[i][j])
                        {
                            dp[i][j] = v;
                            path[i][j] = row[k];
                        }
                    }

                }


            }
        }

        int flag;
        for(int i=0; i<m; i++)
        {
            if(ans>dp[i][0])
            {
                ans = dp[i][0];
                flag = i;
            }
        }

        printf("%d",flag+1);
        for(int i = path[flag][0], j = 1; j < n; i = path[i][j], j++)
            printf(" %d", i+1);
        puts("");
        printf("%d
",ans);


    }



    return 0;
}