HDU3538 A sample Hamilton path

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 503 Accepted Submission(s): 200

Problem Description

Give you a Graph,you have to start at the city with ID zero.

Input

The first line is n(1<=n<=21) m(0<=m<=3)
The next n line show you the graph, each line has n integers.
The jth integers means the length to city j.if the number is -1 means there is no way. If i==j the number must be -1.You can assume that the length will not larger than 10000
Next m lines,each line has two integers a,b (0<=a,b<n) means the path must visit city a first.
The input end with EOF.

Output

For each test case,output the shorest length of the hamilton path.
If you could not find a path, output -1

Sample Input

Sample Output

4
5Hint

I think that all of you know that a!=b and b!=0    =。=

Source

2010 ACM-ICPC Multi-University Training Contest（11）——Host by BUPT

Recommend

zhouzeyong

状态压缩DP，详解见代码

 1 /**/
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<algorithm>
 7 using namespace std;
 8 const int INF=1e6;
 9 const int mxn=4194304;//2^22
10 int dp[mxn][22];//[遍历状态][最后到达点]=最短路径 
11 int dis[22][22];
12 int pre[22];//每个点的前驱要求 
13 int n,m;
14 int xn;
15 int main(){
16     while(scanf("%d%d",&n,&m)!=EOF){
17         memset(pre,0,sizeof pre);
18         int i,j;
19         xn=1<<n;
20         for(i=1;i<xn;i++)
21          for(j=0;j<n;j++){
22              dp[i][j]=INF;
23          }
24         //init
25         for(i=0;i<n;i++)
26          for(j=0;j<n;j++){
27              scanf("%d",&dis[i][j]);
28              if(dis[i][j]==-1)dis[i][j]=INF;
29          }
30         int u,v;
31         for(i=1;i<=m;i++){//保存前驱要求 
32             scanf("%d%d",&u,&v);
33             pre[v]|=(1<<u);
34         }
35         dp[1][0]=0;
36         for(i=1;i<xn;i++){
37             for(j=0;j<n;j++){
38                 if(dp[i][j]==INF)continue;//i状态之前没走到 
39                 for(int k=1;k<n;k++){
40                     if(!(i&(1<<j)))continue;//j不在已走过的集合中
41                     if(i&(1<<k))continue;//k在走过的集合中
42                     if(pre[k]!=(i&pre[k]))continue;//k点前驱要求未满足 
43                     dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+dis[j][k]);
44                 }
45             }
46         }
47         int ans=INF;
48         for(i=0;i<n;i++)ans=min(ans,dp[xn-1][i]);
49         if(ans>=INF) printf("-1
");
50         else printf("%d
",ans);
51     }
52     return 0;
53 }