uva 116Unidirectional TSP【号码塔+打印路径】

主题： uva 116 Unidirectional TSP

意甲冠军：给定一个矩阵，当前格儿童值三个方向回格最小值和当前的和，就第一列的最小值并打印路径（同样则去字典序最小的）、

分析：刚開始想错了，从前往后走，这种话没有办法控制字典序最小，用dfs标记了一下超时了。

事实上从后往前走就好了。

以后一定先想清楚顺序。然后dp的时候选择字典序最小的。用father数据记录就可以。

AC代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include <map>

#include <cmath>

#include <vector>

#include <algorithm>

using namespace std;

const int inf = 0x3f3f3f3f;

int a[12][120],father[12][120];

int main()

{

    int raw,low;

    while(~scanf("%d%d",&raw,&low))

    {

        for(int i=0;i<raw;i++)

            for(int j=0;j<low;j++)

                scanf("%d",&a[i][j]);

        for(int j=low-2;j>=0;j--)

        {

            for(int i=0;i<raw;i++)

            {

                int mi=a[(i+1)%raw][j+1]<a[(i-1+raw)%raw][j+1]?(i+1)%raw:(i-1+raw)%raw;

                if(a[(i+1)%raw][j+1]==a[(i-1+raw)%raw][j+1])

                    mi=min((i+1)%raw,(i-1+raw)%raw);

                if(a[i][j+1]<a[mi][j+1])

                    mi=i;

                else if(a[i][j+1]==a[mi][j+1])

                    mi=min(mi,i);

                a[i][j]+=a[mi][j+1];

                father[i][j]=mi;

            }

        }

        int ma=inf,tmp=0;

        for(int i=0;i<raw;i++)

            if(a[i][0]<ma)

                ma=a[i][0],tmp=i;

        printf("%d",tmp+1);

        for(int j=0;j<low-1;j++)

        {

            printf(" %d",father[tmp][j]+1);

            tmp=father[tmp][j];

        }

        printf("\n%d\n",ma);

    }

    return 0;

}