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

冷不防 2022-08-12 03:29 3阅读 0赞

题目： uva 116Unidirectional 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;
    }