首页 > 代码库 > uva 116 Unidirectional TSP【数塔+打印路径】

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


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