当前位置:网站首页>状态压缩DP AcWing 91. 最短Hamilton路径
状态压缩DP AcWing 91. 最短Hamilton路径
2022-07-03 08:41:00 【T_Y_F666】
状态压缩DP AcWing 91. 最短Hamilton路径
原题链接
算法标签
二进制状态 压缩DP
思路
代码
#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 20, M = 1 << N;
int a[N][N], f[M][N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n=read();
rep(i, 0, n){
rep(j, 0, n){
a[i][j]=read();
}
}
memset(f, 0x3f, sizeof f);
// 在初始点尚未走过任何路程, 因此初始值位0
f[1][0]=0;
// i表示所有的情况
rep(i, 0, 1<<n){
rep(j, 0, n){
// j表示走到哪一个点
if(i>>j&1){// j未走过
// k表示走到j这个点之前,以k为终点的最短距离
rep(k, 0, n){
if(i>>k&1){ //k未走过
f[i][j]=min(f[i][j], f[i-(1<<j)][k]+a[k][j]);
}
}
}
}
}
printf("%lld", f[(1<<n)-1][n-1]);
return 0;
}
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
- Unity editor expansion - draw lines
- Deeply understand the underlying data structure of MySQL index
- Vscode, idea, VIM development tool shortcut keys
- Log4j2 vulnerability recurrence and analysis
- Redux - learning notes
- Markdown directory generation
- Unity editor expansion - window, sub window, menu, right-click menu (context menu)
- The method for win10 system to enter the control panel is as follows:
- 22-06-28 Xi'an redis (02) persistence mechanism, entry, transaction control, master-slave replication mechanism
- 请求参数的发送和接收
猜你喜欢
[concurrent programming] concurrent tool class of thread
PHP uses foreach to get a value in a two-dimensional associative array (with instances)
JS non Boolean operation - learning notes
高斯消元 AcWing 883. 高斯消元解线性方程组
Animation_ IK overview
Analysis of Alibaba canal principle
Gradle's method of dynamically modifying APK package name
第一个Servlet
Unity interactive water ripple post-treatment
【Rust笔记】02-所有权
随机推荐
Markdown learning
22-05-26 Xi'an interview question (01) preparation
Annotations simplify configuration and loading at startup
单调栈-42. 接雨水
Location of package cache downloaded by unity packagemanager
Baidu editor ueeditor changes style
Message queue for interprocess communication
Unity Editor Extension - drag and drop
JS non Boolean operation - learning notes
100 GIS practical application cases (78) - Multi compliance database design and data warehousing
20220630学习打卡
[concurrent programming] concurrent security
Unity editor expansion - draw lines
Gradle's method of dynamically modifying APK package name
[redis] redis persistent RDB vs AOF (source code)
分配异常的servlet
Development material set
PHP mnemonic code full text 400 words to extract the first letter of each Chinese character
How to delete CSDN after sending a wrong blog? How to operate quickly
How to deal with the core task delay caused by insufficient data warehouse resources