题目背景
数据有更改
题目描述
某乡有nn个村庄(1<n \le 201<n≤20)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0<s<1000)s(0<s<1000)是已知的，且AA村到BB村与BB村到AA村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为11，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。
输入输出格式
输入格式：
村庄数nn和各村之间的路程(均是整数)。
输出格式：
最短的路程。
输入输出样例
输入样例#1： 复制
3
0 2 1
1 0 2
2 1 0
输出样例#1： 复制
3 ------------------------------------------------------------
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct pd
{
int ha,e;
}lxy[][];
//存图，ha表示各点时间消耗，e表示要去的点，因为排序动列，不动行，所以记下列，就是要去的点
int hrb[],n,i,j,k,minn=1e9,maxn=,emm[];//新增一个emm数组解决排序动列的问题
int cmp(pd a,pd b)
{
return a.ha<b.ha;
}//排序函数
int ss(int x,int y,int z) //y记录走过的村庄数
{
if(z>=minn)
return ;//用sort优化，提前找出最小值，剪枝
if(z+n-y++maxn>=minn)//两地之间距离最短是1
return ；
//预见性剪枝，maxn表示x点到1的最小距离，然后剩余点取最小值1，极值判定
if(y==n)
{
minn=min(minn,z+emm[x]);
return ;
}
if(y<n)
for(int i=;i<=n;i++)
if(hrb[lxy[x][i].e]==)
//判断是否走过，为啥是lxy[x][i].e,请见上面解释
{
if(z+lxy[x][i].ha+n-y+maxn>minn)
return ;
//预见性剪枝，极值判定，用这两个可以90分
hrb[lxy[x][i].e]=;
ss(lxy[x][i].e,y+,z+lxy[x][i].ha);
hrb[lxy[x][i].e]=;
}
return ;
}
int main()
{
scanf("%d",&n);
for(i=;i<=n;i++)
{
for(k=;k<=n;k++)
{
scanf("%d",&lxy[i][k].ha);
lxy[i][k].e=k;//记录列数
if(i!=&&k==)
maxn=min(maxn,lxy[i][].ha),emm[i]=lxy[i][].ha;
//求x到1的最小时间花费，用于预见性剪枝，和存x到1的花费用于搜索结算，解决排序造成的列乱序的情况
}
sort(lxy[i]+,lxy[i]+n+,cmp);
//STL大法好，二维数组的排序要用for，sort可以优化找出的答案minn，减少无用功
}
hrb[]=;//跑过了就要踩，不然会跑回去，想想80分代码为啥不用赋值为1？因为80分列没乱序
ss(,,);
printf("%d",minn);
return ;
}
这道题吧
标签上是搜索
然而
大部分都是状压dp
但还好
还有写搜索的
（我坚持写搜索的原因就是我搜索不太好）
虽然草草的写了一个
还过了样例
但全wa了
庆幸了一小下
没有tle mle什么的
但当我不太会改的时候
才知道我的搜索是totally错的
向现实低头的我
有卑微看题解了
（题解都在代码中）