acwing-91. 最短Hamilton路径(状态压缩dp)

acwing-91. 最短Hamilton路径(状态压缩dp)给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。输入格式第一行输入整数 n。接下来 n 行每行 n 个整数,其中第 i 行第 j 个整数表示点 i 到 j 的距离(记为 a[i,j])。对于任意的 x,y,z,数据保证 a[x,x]=0,a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。输出格式输出一个整数,表示最短 Ha

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

输入格式
第一行输入整数 n。

接下来 n 行每行 n 个整数,其中第 i 行第 j 个整数表示点 i 到 j 的距离(记为 a[i,j])。

对于任意的 x,y,z,数据保证 a[x,x]=0,a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。

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

数据范围
1≤n≤20
0≤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
#include<bits/stdc++.h>
using namespace std;
const int N = 21;
const int INF = 0x3f3f3f3f;
int f[1 << N][N];
int gg[N][N];
int main(){ 

int n;
scanf("%d",&n);
memset(gg,INF,sizeof gg);
for(int i = 0;i < n;i ++){ 

for(int j = 0;j < n;j ++){ 

scanf("%d",&gg[i][j]);
}
}
memset(f,0x3f,sizeof f);
f[1][0] = 0;
for(int s = 0;s < 1 << n;s ++){ 

for(int u = 0;u < n;u ++){ 

if(!(s >> u & 1))continue;
int pre = s - (1 << u);
for(int k = 0;k < n;k ++){ 

if((pre >> k & 1) && gg[k][u] > 0){ 

f[s][u] = min(f[s][u],f[pre][k] + gg[k][u]);
}
}
}
}
cout<<f[(1 << n) - 1][n - 1]<<endl;
return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168537.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 维基百科(Wikipedia)网址[通俗易懂]

    维基百科(Wikipedia)网址[通俗易懂]分享几个维基百科网址镜像,服务器在国内,可以直接访问,并且打开速度比较快,因镜像网址的原因,搜索的结果也几乎相同,若无法访问国外的维基百科,那就来试试这个吧。

  • 划分数据集python代码_python 字符串类型

    划分数据集python代码_python 字符串类型本文将详细介绍文本分类问题并用Python实现这个过程。引言文本分类是商业问题中常见的自然语言处理任务,目标是自动将文本文件分到一个或多个已定义好的类别中。文本分类的一些例子如下:分析社交媒体中的大众情感 鉴别垃圾邮件和非垃圾邮件 自动标注客户问询 将新闻文章按主题分类更多Python视频、源码、资料加群683380553免费获取目录本文将详细介绍文本分类问题并用Pyt…

  • springBoot+mybatis报错Property ‘sqlSessionFactory’ or ‘sqlSessionTemplate’ are required

    springBoot+mybatis报错Property ‘sqlSessionFactory’ or ‘sqlSessionTemplate’ are required报错为:Invocationofinitmethodfailed;nestedexceptionisjava.lang.IllegalArgumentException:Property’sqlSessionFactory’or’sqlSessionTemplate’arerequired日志很长,报错在末尾2018-07-1213:56:41.760 I…

  • Mybatis事务隔离级别「建议收藏」

    Mybatis事务隔离级别「建议收藏」转载:https://blog.csdn.net/qq924862077/article/details/52599961一般数据库的隔离级别有4个,由低到高依次为Readuncommitted、Readcommitted、Repeatableread、Serializable,这四个级别可以逐个解决脏读、不可重复读、幻读这几类问题。√:可能出现    ×:不会出现脏读不可重复读幻读说明…

    2022年10月14日
  • android调用相册并显示图片_android studio制作简易相册

    android调用相册并显示图片_android studio制作简易相册这是一个打开相册选择图片的故事,不涉及拍照、多图片选择,就是简单的一个单图片选择并展示(不涉及任何权限)。1、activity_main.xml2、MainActivity.java3、下面咱就来运行效果

  • 变量以及数据类型_数据类型定义

    变量以及数据类型_数据类型定义变量以及数据类型变量的相关概念为什么需要变量变量的介绍概念变量使用的基本步骤变量使用注意事项变量的数据类型注意:数据类型相关整型:基本介绍整数的类型整型的使用细节浮点类型基本介绍浮点类型说明一下:浮点型使用细节字符类型基本介绍字符类型使用细节字符类型本质探讨布尔类型基本介绍变量的相关概念为什么需要变量不论是使用哪种高级程序语言编写程序,变量都是其程序的基本组成单位。如下代码:voidmain(){ inta=1;//定义了一个整型变量,取名为a,并赋值为1(强数据类型语言) int

    2022年10月21日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号