UVA 116——Unidirectional TSP

深藏阁楼爱情的钟 2022-08-17 14:09 152阅读 0赞

题意：给定一个n\*m的矩阵，从第一列任意位置向右，右下，右上走一格，可以循环，要求经过的数字的和最小。

思路：记忆化搜索。每次有三个状态，从这三个状态中选择出最优的一个，然后状态累加，保存路径。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    const int N=11;
    const int M=105;
    #define ft(i,s,t) for (int i=s;i<=t;i++)
    #define frt(i,t,s) for (int i=t;i>=s;i--)
    int g[N][M],s[N][M];
    
    int main()
    {
        int n,m,t,tt;
        while (~scanf("%d %d",&n,&m))
        {
            ft(i,0,n-1) ft(j,0,m-1) scanf("%d",&g[i][j]);
    
            frt(j,m-2,0) ft(i,0,n-1)
            {
                int bt=(i+n-1)%n;
                if (g[i][j+1]<g[bt][j+1]||g[i][j+1]==g[bt][j+1]&&bt>i) bt=i; //右上和直走的最优解
                int t=(i+1)%n;
                if (g[t][j+1]<g[bt][j+1]||g[t][j+1]==g[bt][j+1]&&bt>t) bt=t;//右下和全部
    
                g[i][j]+=g[bt][j+1];s[i][j]=bt; //状态记忆和保存路径
            }
    
            int p=n-1;
            frt(i,n-2,0) if (g[p][0]>=g[i][0]) p=i;
            int ans=g[p][0];
            ft(i,0,m-2)
            {
                printf("%d ",p+1);
                p=s[p][i];
            }
    
            printf("%d\n%d\n",p+1,ans);
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关遗传算法解决TSP问题

一、求解问题概述 1.1 TSP问题 TSP问题是指旅行商问题（Traveling Salesman Problem）。在TSP问题中，假设有一名旅行商要在给定的一

向右看齐/ 2024年03月16日 16:23/ 0 赞/ 9 阅读

相关 116.排行榜处理-案例

--图书销售数据表 CREATE TABLE tb( Books nvarchar(30), --书名 Date datetime, -

落日映苍穹つ/ 2024年02月19日 19:02/ 0 赞/ 39 阅读

相关 python系列教程116

朋友们，如需转载请标明出处：[https://blog.csdn.net/jiangjunshow][https_blog.csdn.net_jiangjunshow] 声明

电玩女神/ 2022年08月28日 06:48/ 0 赞/ 184 阅读

相关 UVA 116——Unidirectional TSP

题意：给定一个n\m的矩阵，从第一列任意位置向右，右下，右上走一格，可以循环，要求经过的数字的和最小。思路：记忆化搜索。每次有三个状态，从这三个状态中选择出最优的

深藏阁楼爱情的钟/ 2022年08月17日 14:09/ 0 赞/ 153 阅读

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

题目： uva 116Unidirectional TSP 题意：给出一个矩阵，当前的格子值为后面三个方向的格子最小值和当前的和，就第一列的最小值并打印路径（相同则

冷不防/ 2022年08月12日 03:29/ 0 赞/ 3 阅读

相关 tsp问题——遗传算法解决

TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）！。可以形象地把解空间看成是一个无

小鱼儿/ 2022年08月04日 08:29/ 0 赞/ 204 阅读

相关 uva 116 数塔动态规划

横着的数塔，从左往右走，可以走右上，右，右下三个方向，最后一行往右下走可以穿越到第一行，第一行往右上走可以穿越到最后一行。最后要求输出走的路径以及路径和的最小值，

亦凉/ 2022年08月03日 13:41/ 0 赞/ 203 阅读

相关 UVA 116(单向TSP)

题目来源:[点击打开链接][Link 1] 题目题意:题目给我们一个m\n的数阵，我们从第一列的任何位置出发，每次只能向右，右上，右下前进，到达最后一列，且矩阵式环形的，求经

爱被打了一巴掌/ 2022年06月07日 02:40/ 0 赞/ 159 阅读

相关动态规划求解TSP圈

求解思路：动态规划的方法的最大难点就在于初始变量的确定，选择合适的初始变量才能更好的运用动态规划的方式解决问题。我在这里定义的变量就是d(i,S),

痛定思痛。/ 2022年04月25日 09:30/ 0 赞/ 231 阅读

相关 UVa116 Unidirectional TSP 多段图的最短路

题意：给定一个n\m的矩阵，要求从第一列的任何一行出发，每次沿右或右下或右上到达后面一列，最后到第m列任何一行整个路程的最小值，并且要求是字典序最小的。分析：阶段很明

向右看齐/ 2021年12月19日 02:25/ 0 赞/ 195 阅读