首页 > 代码库 > 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【数塔+打印路径】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。