首页 > 代码库 > 状压DP [SWUST OJ 411] 售货员的难题

状压DP [SWUST OJ 411] 售货员的难题

售货员的难题(0411)

Time limit(ms): 5000 Memory limit(kb): 65535 Submission: 1744 Accepted: 200

Description

某乡有n个村庄(1< n < 20),有一个售货员,他要到各个村庄去售货,各村庄之间的路程s(0 < s < 1000)是已知的,且A村到B村与B村到A村的路大多不同。为了提高效率,他从商店出发到每个村庄一次,然后返回商店所在的村,假设商店所在的村庄为 1,他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。

Input

村庄数n和各村之间的路程(均是整数)。

Output

最短的路程

Sample Input

3 {村庄数}
0 2 1 {村庄1到各村的路程}
1 0 2 {村庄2到各村的路程}
2 1 0 {村庄3到各村的路程}
 

Sample Output
 
3
 
TSP原题、没什么好说的、注意运算符优先级,(好吧、我承认忘了加一个括号,WA了N次)
#include <iostream>#include <cstdio>#include <cstring>using namespace std;#define INF 0x3f3f3f3f int n;int mpt[20][20];int dp[20][1<<20]; void solve(){    int i,j,k,MAX=1<<n;    memset(dp,INF,sizeof(dp));    for(i=0;i<n;i++)    {        dp[i][1<<i]=mpt[0][i];    }    for(j=0;j<MAX;j++)    {        for(i=0;i<n;i++)        {            if((j&(1<<i))==0) continue;  //注意运算符优先级            for(k=0;k<n;k++)            {                dp[i][j]=min(dp[i][j],dp[k][j&(~(1<<i))]+mpt[k][i]);            }        }    }    printf("%d\n",dp[0][MAX-1]);}int main(){    while(scanf("%d",&n)!=EOF)    {        for(int i=0;i<n;i++)        {            for(int j=0;j<n;j++)            {                scanf("%d",&mpt[i][j]);            }        }        solve();    }    return 0;}

 

 
 

状压DP [SWUST OJ 411] 售货员的难题