首页 > 其他分享 >最短Hamilton路径(状态压缩DP)

最短Hamilton路径(状态压缩DP)

时间:2024-03-27 13:31:30浏览次数:27  
标签:int 路径 整数 最短 ++ Hamilton DP 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]。

输出格式

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

数据范围

1≤n≤20
0≤a[i,j]≤10e7

输入样例:
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

思路:

用二进制来表示要走的所以情况的路径,这里用i来代替
例如走0,1,2,4这三个点,则表示为:10111;
走0,2,3这三个点:1101;
状态表示:f[i][j];
集合:所有从0走到j,走过的所有点的情况是i的所有路径
属性:MIN
状态计算:如1中分析一致,0–>·····–>k–>j中k的所有情况

状态转移方程:dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + w[k][j])

#include <iostream>
#include <cstring>

using namespace std;

const int N = 20;

int n;
int w[N][N], dp[1 << N][N];

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            cin >> w[i][j];
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for (int i = 0; i < 1 << n; i ++ ) {
        for (int j = 0; j < n; j ++ ) {
            if (i >> j & 1) 
                for (int k = 0; k < n; k ++ ) {
                    if (i >> k & 1) {
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + w[k][j]);
                    }
                }
        }
    }
    cout << dp[(1 << n) - 1][n - 1] << endl;
}

标签:int,路径,整数,最短,++,Hamilton,DP,dp
From: https://blog.csdn.net/chq66666/article/details/137074238

相关文章

  • 管道(NamedPipeClientStream)连接报“访问路径被拒绝”
    问题:NamedPipeClientStream对象调用Connect(毫秒)时报“访问路径被拒绝”解决:在服务端(NamedPipeServerStream)中添加PipeSecurity对象SecurityIdentifiersecurityIdentifier=newSecurityIdentifier(WellKnownSidType.AuthenticatedUserSid,null);PipeSecuritypipeSecur......
  • 十九 731. 毕业旅行问题 (状态压缩DP)
    731.毕业旅行问题(状态压缩DP)思路:使用状态压缩DP,dp[i][j]中i表示状态(二进制表示),j表示最后所在城市。算法时间复杂度是O(2n*n2),需要优化掉没有访问过1号城市的状态和无效状态。importjava.util.*;publicclassMain{privatestaticintn;privatestaticint......
  • 蓝桥杯练习题总结(三)线性dp题(摆花、数字三角形加强版)
    目录 一、摆花思路一: 确定状态:初始化:思路二:确定状态:初始化:循环遍历: 状态转移方程: 二、数字三角形加强版一、摆花题目描述小明的花店新开张,为了吸引顾客,他想在花店的门口摆上一排花,共m盆。通过调查顾客的喜好,小明列出了顾客最喜欢的n种花,从1到n标号。为了......
  • 数位dp
    233.数字1的个数给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。classSolution:defcountDigitOne(self,n:int)->int:s=str(n)@cachedeff(i:int,cnt:int,is_limit:bool)->int:ifi==len(s):......
  • PTA最短距离的两点
    给出一些整数对,它们表示平面上的点,求所有这些点中距离最近的两个点。输入格式:测试数据有多组。对于每组测试,先输入一个整数N,表示点的个数,再输入N个点(以两个整数表示横纵坐标)。若N为0,则表示输入结束。输出格式:对于每组测试,输入所有点中距离最短的两点,格式为“(a,b)(......
  • 高维前缀和/SOS DP 学习笔记
    JOISC2023D2T2Council注意到,钦定一个人为主席后,对于此时得票数大于\(\lfloor\frac{n}{2}\rfloor\)的议案,不管怎么选副主席,均能通过;对于此时得票数小于\(\lfloor\frac{n}{2}\rfloor\)的议案,不管怎么选副主席,均不能通过。所以需要考虑的只有此时得票数恰好等于\(\lfloo......
  • 动态规划——线性dp
    数字三角形//从上到下#include<iostream>#include<algorithm>usingnamespacestd;constintN=510,INF=1e9;intn;inta[N][N];intf[N][N];intmain(){scanf("%d",&n);for(inti=1;i<=n;i++)for(int......
  • 使用dpkg在ubuntu上安装软件包遇到依赖包的问题
    问题在ubuntu上使用apt-get安装软件包,系统会自动安装依赖的软件包,但是使用dpkg在ubuntu上安装软件包时不会,有时会遇到下面的错误:pengdl@pengdl-HP:~/Soft$sudodpkg-ivirtualbox-7.0_7.0.14-161095~Ubuntu~focal_amd64.deb[sudo]passwordforpengdl:Selectingpreviously......
  • 换根DP学习笔记
    啊啊啊啊啊啊啊啊啊啊啊啊画图累死我了额,这不菜根快乐DP(根)吗换根DP,即换根树形DP平常树形DP指定一个根,但万一邪恶出题人让你求多个点为根的情况呢?你们可能会想:多跑几遍不就好了!不可以的,直接TLE。这有个树,B是A之后的树根(拎上去):B成为树根后:画风突然转变但是!其实有些没变!......
  • 【DP】01背包问题与完全背包问题
    一、01背包问题有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi,价值是 wi。求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。输出最大价值。输入格式第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包......