不重不漏走完所有节点(我全都要!)
换句话说就是到达最后节点时其它的节点都走完了
然后可以用状态压缩动态规划
这道题放在初始之章, 目的是让我们学会利用位运算将整数当成集合来用。
不要跑偏而陷入到无谓的思考当中去, 重点是整数当集合用的各种操作!!!
#include<bits/stdc++.h>
using namespace std;
const int maxn = 21;
int n, a[maxn][maxn];
int f[1 << maxn][maxn];
bool is_in(int S, int node)
{
return (S >> (node-1)) & 1 ;
}
int main()
{
cin >> n; for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) cin >> a[i][j];
memset(f, 63, sizeof f);
f[1][1] = 0;
for(int nowset = 1; nowset < (1<<n); ++nowset)
for(int now=1; now<=n; ++now)
if( is_in(nowset, now) )
for(int pre=1; pre<=n; ++pre)
if( is_in(nowset, pre) )
{
int preset = nowset ^ (1 << (now-1));
f[nowset][now] = min(f[nowset][now], f[preset][pre] + a[pre][now]);
}
cout << f[(1<<n)-1][n] ;
return 0;
}
原文链接: https://www.cnblogs.com/tztqwq/p/12238225.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/325632
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!