@[i099i1aa6c](/user/752021) 试着把一些int改成unsigned int
by TLEWA @ 2022-07-29 23:24:12
还有
```cpp
//#define FIO //开启加速模式 将不能使用键盘读入
```
这一行，你注释起来了:（
by TLEWA @ 2022-07-29 23:25:08
@[i099i1aa6c](/user/752021) 我的记忆化搜索不开O2，没加快读都过了
https://www.luogu.com.cn/record/75899838
by TLEWA @ 2022-07-29 23:26:51
@[i099i1aa6c](/user/752021) 可以排个序，将路程短的排在前面，减小无用搜索树
by TLEWA @ 2022-07-29 23:28:09
@[i099i1aa6c](/user/752021) 还可以加inline(虽然我就没加
by TLEWA @ 2022-07-29 23:29:02
@[i099i1aa6c](/user/752021) 加几个剪枝
by TLEWA @ 2022-07-29 23:29:46
```cpp
#include<bits/stdc++.h>
#pragma GCC target ("popcnt") //这条GCC指令可以让__builtin_popcount被编译器识别为一条指令
#define bffs(x) __builtin_ffs(x) //返回x的二进制下第一位1的位置(从1开始)
#define bclz(x) __builtin_clz(x) //返回x二进制下最高有效位到最高位的1上一位的长度（即最高位开始连续0的个数）
#define bcyz(x) __builtin_ctz(x) //与上一个函数相反，返回x的二进制下最低位开始连续0的个数（即第一个函数 - 1）
#define bpar(x) __builtin_parity(x) //返回x二进制下1的个数的奇偶性
#define bpop(x) __builtin_popcount(x) //返回x二进制下1的个数
using namespace std;
const int numarr[21]={0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};
int n,minn=(1<<30),dparr[1050000][20];
struct road{
int to; //去哪
int distance; //路程
}arr[25][25];
bool cmp(road x,road y){
return x.distance<y.distance;
}
void dp_(int last,int now,int sumn);
void dp(int last,int now,int sumn){
if(dparr[last][now]&&sumn>=dparr[last][now]) return;
dparr[last][now]=sumn;
dp_(last,now,sumn);
return;
}
void dp_(int last,int now,int sumn){
// cout << (last>>(now-1))%2 << endl;
if(last%2){
if(bpop(last)==n && minn>sumn) {
minn=sumn;
// cout << last << endl;
}
return;
}
if(sumn>=minn || (last>>(now-1))%2==1) return;
for(int i=1;i<=n;++i){
if( (last>>(arr[now][i].to-1)) % 2==0 ){
dp(last+numarr[now],arr[now][i].to,sumn+arr[now][i].distance);
}
}
}
int main(){
cin >> n;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
cin >> arr[i][j].distance;
arr[i][j].to=j;
}
}
for(int i=1;i<=n;++i) sort(arr[i]+1,arr[i]+1+n,cmp);
for(int i=2;i<=n;++i){
dp(0,arr[1][i].to,arr[1][i].distance);
}
cout << minn;
return 0;
}
```
我的代码
by TLEWA @ 2022-07-29 23:30:09
@[TLEWA](/user/515129) 谢谢 不过那个加速快读提交的时候我是打开的 我去卡卡常
by i099i1aa6c @ 2022-07-30 09:54:26
@[TLEWA](/user/515129) 谢谢奆佬 已经A了
加了那个排序的魔法优化
```cpp
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
//#define FIO //开启加速模式 将不能使用键盘读入
struct IO{
#ifdef FIO
const static int BUFSIZE=1<<20;char buf[BUFSIZE],obuf[BUFSIZE],*p1,*p2,*pp;inline char gc(){return(p1==p2&&(p2=(p1=buf)+fread(buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++);}inline void pc(char x){((pp-obuf==BUFSIZE&&(fwrite(obuf,1,BUFSIZE,stdout),pp=obuf)),*pp=x,pp++);}inline void flush(){fwrite(obuf,1,pp-obuf,stdout);}IO(){p1=buf,p2=buf,pp=obuf;}~IO(){fwrite(obuf,1,pp-obuf,stdout);}
#else
int(*gc)()=&getchar;int(*pc)(int)=&putchar;inline void flush(){};
#endif
template<typename Tp=int>inline Tp read(){Tp s=0;int f=1;char ch=gc();while(!isdigit(ch))f=(ch=='-'?-1:1),ch=gc();while(isdigit(ch))s=s*10+(ch^48),ch=gc();return s*f;}template<typename Tp>void read(Tp&x){x=read();}template<typename Tp,typename...Ts>void read(Tp&x,Ts&...val){x=read<Tp>();read(val...);}template<typename Tp>void write(Tp x){if(x<0)pc('-'),x=-x;static char sta[20];int top=0;do sta[top++]=x%10+'0',x/=10;while(x);while(top)pc(sta[--top]);}template<typename Tp,typename...Ts>void write(Tp x,Ts...val){write(x);pc(' ');write(val...);}template<typename...Ts>void writeln(Ts...val){write(val...);pc('\n');}}io;
struct Edge{
int to,weight;
}arr[30][30];
int n,max_state,mem[30][1<<20|1];
int dfs(int u,int state){
if(state==max_state) return u==1?0:0x3f3f3f3f;
if(state&1) return 0x3f3f3f3f;
if(mem[u][state]!=-1) return mem[u][state];
int res = 2147483647;
for(int i=1;i<=n;i++){
int v = arr[u][i].to;
if(v!=u&&!(state>>(v-1)&1))
res = min(res,dfs(v,state|(1<<(v-1)))+arr[u][i].weight);
}
return mem[u][state] = res;
}
int main(){
memset(mem,-1,sizeof(mem));
n = io.read(),max_state = (1 << n) - 1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
arr[i][j].weight = io.read(),arr[i][j].to = j;
for(int i=1;i<=n;i++)
sort(arr[i]+1,arr[i]+1+n,[](auto a,auto b){return a.weight < b.weight;});
io.writeln(dfs(1,0));
return 0;
}
```
by i099i1aa6c @ 2022-07-30 10:12:47