当前位置: 首页 > news >正文

Acwing.91 最短Hamilton路径(动态规划)

题目

给定一张n个点的带权无向图,点从0~n-1标号,求起点0到终点n-1的最短Hamilton路径。Hamilton路径的定义是从0到n-1不重不漏地经过每个点恰好一次。

输入格式

第—行输入整数n。
接下来n行每行n个整数,其中第i行第j个整数表示点i到j的距离(记为a[i.i])。对于任意的, y,z,数据保证a[x,x]=0,a[x,y]=a[y,x]并且a[x,y]+aly,z]>=a[x,z]。

输出格式

输出一个整数,表示最短Hamilton路径的长度。

数据范围

1 ≤n ≤200≤a[i,j≤107

  • 输入样例
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
  • 输出样例:
18

题解

import java.util.Arrays;
import java.util.Scanner;/*** @author akuya* @create 2023-07-28-20:56*/
public class hamiltion {static int N=20;static int M=1<<N;static int n;static int w[][]=new int[N][N];static int f[][]=new int[M][N];public static void main(String[] args) {Scanner scanner=new Scanner(System.in);n=scanner.nextInt();for(int i=0;i<n;i++)for (int j = 0; j < n; j++)w[i][j]=scanner.nextInt();for(int i=0;i<M;i++){Arrays.fill(f[i],0x3f);}f[1][0]=0;for(int i=0;i<1<<n;i++)for(int j=0;j<n;j++)if((i>>j&1)!=0)for(int k=0;k<n;k++)if(((i-(1<<j))>>k&1)!=0)f[i][j]=Math.min(f[i][j],f[i-(1<<j)][k]+w[k][j]);System.out.println(f[(1<<n)-1][n-1]);}
}

思路

本题同样是状态压缩类的动态规划,具体思路如下图
在这里插入图片描述
i代表走过的点,状态转移用到达j点的倒数第二个点,转移方程得出为

f[i][j]=Math.min(f[i][j],f[i-(1<<j)][k]+w[k][j]);

注意边界条件即可

相关文章:

Acwing.91 最短Hamilton路径(动态规划)

题目 给定一张n个点的带权无向图&#xff0c;点从0~n-1标号&#xff0c;求起点0到终点n-1的最短Hamilton路径。Hamilton路径的定义是从0到n-1不重不漏地经过每个点恰好一次。 输入格式 第—行输入整数n。 接下来n行每行n个整数&#xff0c;其中第i行第j个整数表示点i到j的距…...

[hfut] [important] v4l2 vedio使用总结/opevx/ffpeg/v4l2/opencv/cuda

(158条消息) linux驱动camera//test ok_感知算法工程师的博客-CSDN博客 (158条消息) linux V4L2子系统——v4l2架构&#xff08;1&#xff09;之整体架构_感知算法工程师的博客-CSDN博客 (158条消息) linux V4L2子系统——v4l2的结构体&#xff08;2&#xff09;之video_devi…...

2023年深圳杯数学建模A题影响城市居民身体健康的因素分析

2023年深圳杯数学建模 A题 影响城市居民身体健康的因素分析 原题再现&#xff1a; 以心脑血管疾病、糖尿病、恶性肿瘤以及慢性阻塞性肺病为代表的慢性非传染性疾病&#xff08;以下简称慢性病&#xff09;已经成为影响我国居民身体健康的重要问题。随着人们生活方式的改变&am…...

指令调度(Instruction Scheduling)

指令调度&#xff08;Instruction Scheduling&#xff09; 指令调度的约束基本机器模型基本块调度全局调度 指令调度是为了提高指令级并行&#xff08;ILP&#xff09;&#xff0c;对于超长指令字&#xff08;VLIW, Very Long Instruction Word&#xff09;和多发射系统&#x…...

【运维】Linux 跨服务器复制文件文件夹

【运维】Linux 跨服务器复制文件文件夹 如果是云服务 建议用内网ip scp是secure copy的简写&#xff0c;用于在Linux下进行远程拷贝文件的命令&#xff0c;和它类似的命令有cp&#xff0c;不过cp只是在本机进行拷贝不能跨服务器&#xff0c;而且scp传输是加密的。可能会稍微影…...

k8s apiserver如何支持http访问?

原本是可以通过设置api-server的--insecure-port来实现&#xff0c;但是这个参数已经被废弃了&#xff0c;更好的方法则是使用proxy来实现&#xff1a; 在集群任意一个节点上起一个proxy服务&#xff0c;并设置允许所有host访问&#xff1a; kubectl proxy --address0.0.0.0 …...

Safetensors,高效安全易用的深度学习新工具

大家好&#xff0c;本文将介绍一种为深度学习应用提供速度、效率、跨平台兼容性、用户友好性和安全性的新工具。 Safetensors简介 Hugging Face开发了一种名为Safetensors的新序列化格式&#xff0c;旨在简化和精简大型复杂张量的存储和加载。张量是深度学习中使用的主要数据…...

Unity 工具之 NuGetForUnity 包管理器,方便在 Unity 中的进行包管理的简单使用

Unity 工具之 NuGetForUnity 包管理器&#xff0c;方便在 Unity 中的进行包管理的简单使用 目录 Unity 工具之 NuGetForUnity 包管理器&#xff0c;方便在 Unity 中的进行包管理的简单使用 一、简单介绍 二、NuGetForUnity 的下载导入 Unity 三、NuGetForUnity 在 Unity 的…...

运算放大器(二):恒流源

一、实现原理 恒流源的输出电流能够在一定范围内保持稳定&#xff0c;不会随负载的变化而变化。 通过运放&#xff0c;将输入的电压信号转换成满足一定关系的电流信号&#xff0c;转换后的电流相当一个输出可调的简易恒流源。 二、电路结构 常用的恒流源电路如…...

企业选择租用CRM还是一次性买断CRM?分别有哪些优势?

CRM是企业管理客户关系&#xff0c;提升销售业绩&#xff0c;实现业务增长的重要工具。市场上的CRM系统销售方式主要有两种——租用型和买断型。那么&#xff0c;租用CRM好还是一次性买断CRM好&#xff1f;本文将从以下几个方面进行分析&#xff1a; 1、什么是租用型CRM和买断…...

VBA_MF系列技术资料1-133

MF系列VBA技术资料 为了让广大学员在实际VBA编程中有切实可行的思路及有效的提高自己的编程技巧&#xff0c;我参考大量的资料&#xff0c;并结合自己的经验总结了这份MF系列VBA技术综合资料&#xff0c;而且开放源码&#xff08;MF04除外&#xff09;&#xff0c;其中MF01-04属…...

Android 项目架构

🔥 什么是架构 🔥 在维基百科里是这样定义的: 软件架构是一个系统的轮廓 . 软件架构描述的对象是直接构成系统的抽象组件. 各个组件之间的连接则明确和相对细致地描述组件之间的通讯 . 在实现阶段, 这些抽象组件被细化为实际组件 , 比如具体某个类或者对象 . 面试的过程中…...

【Linux】进程通信 — 管道

文章目录 &#x1f4d6; 前言1. 通信背景1.1 进程通信的目的&#xff1a;1.2 管道的引入&#xff1a; 2. 匿名管道2.1 匿名管道的原理&#xff1a;2.2 匿名管道的创建&#xff1a;2.3 父子进程通信&#xff1a;2.3.1 read()阻塞等待 2.4 父进程给子进程派发任务&#xff1a;2.5…...

ROS 2 — 托管(生命周期)节点简介

一、说明 这篇文章是关于理解ROS 2中托管&#xff08;生命周期&#xff09;节点的概念。我们描述了概念性的想法以及我们为什么需要它。所以让我们开始吧&#xff01; 二、托管式节点 — 什么和为什么&#xff1f; 为了理解托管式节点&#xff0c;让我们从一个简单的问题陈述开…...

vue2企业级项目(六)

vue2企业级项目&#xff08;六&#xff09; 自定义指令 创建src/directive/index.js const directives require.context("./modules", true, /\.js$/);export default {install: (Vue) > {directives.keys().forEach((key) > {let directive directives(key…...

OSPF的选路原则

域内 --- 1类&#xff0c;2类LSA 域间 --- 3类LSA 域外 --- 5类&#xff0c;7类LSA --- 根据开销值的计算规则不同&#xff0c;还分为类型1和类型2 1.如果学到的路由都是通过1类&#xff0c;2类LSA获取的域内路由 --- 这种情况直接比较开销值&#xff0c;优先选择开销值小的路…...

4.操作元素属性

4.1操作元素常用属性 ●通过 JS 设置/修改 标签元素属性&#xff0c;比如通过src更换图片 ●最常见的属性比如&#xff1a;href、 title、 src 等 ●语法: 对象.属性 值【示例】 // 1.获取元素 const pic document.querySelector( img ) // 2.操作元素 pic.src ./images/b…...

uniapp 微信小程序:v-model双向绑定问题(自定义 props 名无效)

uniapp 微信小程序&#xff1a;v-model双向绑定问题&#xff08;自定义 props 名无效&#xff09; 前言问题双向绑定示例使用 v-model使用 v-bind v-on使用 sync 修饰符 参考资料 前言 VUE中父子组件传递数据的基本套路&#xff1a; 父传子 props子传父 this.$emit(事件名, …...

【Lua学习笔记】Lua进阶——Table(3) 元表

接上文 文章目录 元表__tostring__call__index__newindex运算符元方法其它元表操作 元表 Q&#xff1a;为什么要使用元表&#xff1f; A&#xff1a;在Lua中&#xff0c;常常会需要表与表之间的操作。元表中提供了一些元方法&#xff0c;通过自定义元方法可以实现想要的功能&…...

AI编程常用工具 Jupyter Notebook

点击上方蓝色字体&#xff0c;选择“设为星标” 回复”云原生“获取基础架构实践 深度学习编程常用工具 我们先来看 4 个常用的编程工具&#xff1a;Sublime Text、Vim、Jupyter。虽然我介绍的是 Jupyter&#xff0c;但并不是要求你必须使用它&#xff0c;你也可以根据自己的喜…...

Axure RP 中文语言包:3分钟消除语言障碍,释放原型设计效率

Axure RP 中文语言包&#xff1a;3分钟消除语言障碍&#xff0c;释放原型设计效率 【免费下载链接】axure-cn Chinese language file for Axure RP. Axure RP 简体中文语言包&#xff0c;不定期更新。支持 Axure 9、Axure 10。 项目地址: https://gitcode.com/gh_mirrors/ax/…...

Windows 11 + Ubuntu 20.04双系统安装避坑指南(附分区方案)

Windows 11与Ubuntu 20.04双系统安装全流程精解 对于想要在现有Windows 11系统上体验Ubuntu的用户来说&#xff0c;双系统安装是最佳选择。这种方式既能保留熟悉的Windows环境&#xff0c;又能探索Linux世界的无限可能。本文将详细解析从准备到安装的完整流程&#xff0c;特别针…...

大模型上下文长度的优化策略与应用场景

1. 大模型上下文长度的本质与挑战 当你和ChatGPT聊天时&#xff0c;有没有遇到过它突然"失忆"的情况&#xff1f;比如聊到第20轮对话时&#xff0c;它完全忘记了开头讨论的主题。这就是上下文长度限制导致的典型问题。所谓上下文长度&#xff0c;就是大模型能够记住和…...

4大维度解锁TrafficMonitor插件扩展能力:定制化系统监控全攻略

4大维度解锁TrafficMonitor插件扩展能力&#xff1a;定制化系统监控全攻略 【免费下载链接】TrafficMonitorPlugins 用于TrafficMonitor的插件 项目地址: https://gitcode.com/gh_mirrors/tr/TrafficMonitorPlugins 价值定位&#xff1a;为什么需要TrafficMonitor插件系…...

WPF拖拽实战避坑指南:从DragDropEffects到QueryContinueDrag,解决拖拽后鼠标事件失效的诡异问题

WPF拖拽实战避坑指南&#xff1a;从DragDropEffects到QueryContinueDrag&#xff0c;解决拖拽后鼠标事件失效的诡异问题 当你在WPF项目中实现拖拽功能时&#xff0c;是否遇到过这样的场景&#xff1a;拖拽操作完成后&#xff0c;控件的MouseMove事件突然"失灵"&#…...

基于CLIP-GmP-ViT-L-14的智能教学辅助:自动化作业批改场景构想

基于CLIP-GmP-ViT-L-14的智能教学辅助&#xff1a;自动化作业批改场景构想 最近和几位做教师的朋友聊天&#xff0c;他们都在抱怨同一件事&#xff1a;批改作业&#xff0c;尤其是那种需要看图说话的作业&#xff0c;实在太费时间了。一个班几十个学生&#xff0c;每个学生交上…...

python汽车4s店的汽车租赁服务管理系统vue

目录功能模块分析租赁服务核心功能技术实现要点扩展功能建议项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作功能模块分析 用户管理模块 用户注册与登录&#xff1a;支持手机号、邮箱注册&#xff0c;集成短信验证码功能。权限…...

uniapp中集成leaflet地图的3个坑与解决方案(附完整代码)

uniapp中集成leaflet地图的3个坑与解决方案&#xff08;附完整代码&#xff09; 在移动端开发领域&#xff0c;uniapp因其跨平台特性广受欢迎&#xff0c;而leaflet作为轻量级地图库也备受青睐。但当两者结合时&#xff0c;开发者往往会遇到一些意想不到的挑战。本文将深入剖析…...

告别死记硬背!信息系统项目管理师(高项)思维导图活用法:从考前3个月到考前一天的全周期规划

信息系统项目管理师备考革命&#xff1a;用思维导图构建你的动态知识引擎 备考信息系统项目管理师&#xff08;高项&#xff09;的过程&#xff0c;常常让考生陷入两难困境&#xff1a;一方面要掌握庞杂的知识体系&#xff0c;另一方面又要应对实际工作中的时间压力。传统死记硬…...

掌握通达信数据接口:量化分析从入门到精通

掌握通达信数据接口&#xff1a;量化分析从入门到精通 【免费下载链接】mootdx 通达信数据读取的一个简便使用封装 项目地址: https://gitcode.com/GitHub_Trending/mo/mootdx 解决量化数据获取难题&#xff1a;MOOTDX的技术方案与实战应用 如何突破量化分析的数据获取…...