2596 售货员的难题
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 钻石 Diamond
题目描述 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入门题
f[i][j]表示当前状态为i,走到第j个城市最短路径
相应的状态转移方程为f[i][j]=min( f[i^(1<<j)][k]+g[k][j]);
i^(1<<j)的意思是将j这个城市从i状态中去掉.g[k][j]是k和j之间的距离。
*/
#include<iostream>
#include<cstdio>
#include<cstring> #define maxn 50010 using namespace std;
int n,g[][],f[maxn][],ans; int min(int x,int y){return x<y?x:y;} int main()
{
scanf("%d",&n);n--;
memset(f,/,sizeof(f));
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&g[i][j]);
ans=f[][];f[][]=;
for(int i=;i<(<<n);i++)
for(int j=;j<=n;j++)if(i&(<<j-))
for(int k=;k<=n;k++)
f[i][j]=min(f[i][j],f[i^(<<j-)][k]+g[k][j]);
for(int i=;i<=n;i++)
ans=min(ans,f[(<<n)-][i]+g[i][]);
printf("%d\n",ans);
return ;
}