题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int N=20,M=1<<20;//前面那个指的是数组中的元素个数,后面那个表示的是所有的情况
int w[N][N];
int f[M][N];//这个存放的是dp的状态
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>w[i][j];
}
}
f[1][0]=0;//表示当前仅仅只是走过(0)点 前面的1表示的是 1<<0=1 表示当前0这个点已经走过
memset(f,0x3f,sizeof f);
f[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-(1<<j))>>k&1){
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
}
}
}
}
}
cout<<f[(1<<n)-1][n-1];
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla