题目描述 Description
某乡有n个村庄(1<n<＝15)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0<s<1000)是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。
输入描述 Input Description
村庄数n和各村之间的路程(均是整数)
输出描述 Output Description
最短的路程
样例输入 Sample Input
3
0 2 1
1 0 2
2 1 0
样例输出 Sample Output
3
数据范围及提示 Data Size & Hint
本题可用最短路思想、搜索来解决，但是可能无法通过一组极限数据（且效率较低）。建议按树状DP考虑！
/*
不会什么树形DP，我做的是spfa（其实floyed就可以）+深搜+剪枝
首先将边反向，spfa处理所有点到1的距离，以备剪枝使用
然后深搜得到答案
剪枝：利用spfa得到的距离，当当前的dis+(n-t)*minn+f[x]>ans时，剪枝
（minn是矩阵中的最短距离，n-t是还有几步可以遍历完所有的村庄）
*/
#include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
#define M 20
#define INF 3000000
using namespace std;
int map[M][M],f[M],n,ans=INF,min1=INF;
int a2[M][M];
bool vis[M];
queue<int> q;
int read()
{
char c=getchar();int num=,flag=;
while(c<''||c>''){if(c=='-')flag=-;c=getchar();}
while(c>=''&&c<=''){num=num*+c-'';c=getchar();}
return num*flag;
}
void dfs(int x,int t,int dis)
{
if(dis>ans)return;
if(dis+(n-t)*min1+f[x]>ans)return;
if(t==n)
{
ans=min(ans,dis+map[x][]);
return;
}
for(int i=;i<=n;i++)
if(!vis[i])
{
vis[i]=true;
dfs(i,t+,dis+map[x][i]);
vis[i]=false;
}
}
void spfa()
{
q.push();
vis[]=;
f[]=;
while(!q.empty())
{
int x=q.front();
q.pop();
vis[x]=;
for(int i=;i<=n;i++)
if(a2[x][i]&&f[x]+a2[x][i]<f[i])
{
f[i]=f[x]+a2[x][i];
if(!vis[i])
{
vis[i]=;
q.push(i);
}
}
}
}
int main()
{
memset(f,0x3f3f3f3f,sizeof(f));
n=read();
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
map[i][j]=read();
a2[j][i]=map[i][j];
min1=min(min1,map[i][j]);
}
spfa();
memset(vis,,sizeof(vis));
vis[]=;
dfs(,,);
printf("%d",ans);
return ;
}