Acwing-91-最短Hamilton路径(状压DP)

2021-02-04 21:15

阅读：364

标签：href content its ace ret can mes 无向图 pac

链接:

https://www.acwing.com/problem/content/93/

题意:

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

思路:

用二进制枚举哪些点被经过了.同时枚举经过的点j,再枚举经过点j之前的点k.
得到Dp[i][j] = min(Dp[i][j], Dp[lasti][k]+Len[k][j]).其中i对应经过点j时的压缩值,lasti为经过点j上一时刻的压缩值.

代码:

#include 
using namespace std;

int F[1> j) & 1)
            {
                for (int k = 0;k > k & 1)
                        F[i][j] = min(F[i][j], F[i^(1

Acwing-91-最短Hamilton路径(状压DP)

标签：href content its ace ret can mes 无向图 pac

原文地址：https://www.cnblogs.com/YDDDD/p/11456367.html

上一篇：大幅提升Delphi Datasnap数据传输效率的方法

下一篇：持续集成高级篇之基于win32-openssh搭建jenkins混合集群(一)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Acwing-91-最短Hamilton路径(状压DP)
文章链接：http://soscw.com/index.php/essay/51067.html

亲，登录后才可以留言！

Acwing-91-最短Hamilton路径(状压DP)

链接:

题意:

思路:

代码:

评论

热门文章

推荐文章

最新文章

置顶文章