首页 > > 程序设计 > C/C++ >

Travelling HDU - 3001

2018-06-17 21:49:10来源：未知阅读 ()

方法：3进制状态压缩dp（更好的方法是预处理出每个状态数字对应的y数组，然后用刷表，时间复杂度可以少一个n）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 LL n,m,anss=0x3f3f3f3f3f3f3f3f;
 7 LL y[20];
 8 LL dis[20][20];
 9 LL ans[100000][20];
10 void split(LL x,LL y[])
11 {
12     for(LL i=1;i<=n;i++)
13     {
14         y[i]=x%3;
15         x/=3;
16     }
17 }
18 LL merge(LL y[])
19 {
20     LL ans=0,i,base=1;
21     for(i=1;i<=n;i++)
22         ans+=y[i]*base,base*=3;
23     return ans;
24 }
25 int main()
26 {
27     LL i,j,kk,k,a,b,c,p;
28     bool flag;
29     while(scanf("%lld%lld",&n,&m)==2)
30     {
31         anss=0x3f3f3f3f3f3f3f3f;
32         memset(dis,0x3f,sizeof(dis));
33         memset(ans,0x3f,sizeof(ans));
34         for(i=1;i<=m;i++)
35         {
36             scanf("%lld%lld%lld",&a,&b,&c);
37             dis[a][b]=min(dis[a][b],c);
38             dis[b][a]=min(dis[b][a],c);
39         }
40         for(i=0;i<=n;i++)
41         {
42             dis[0][i]=dis[i][0]=0;
43             dis[i][i]=0;
44         }
45         for(i=1;i<=n;i++)
46             y[i]=2;
47         kk=merge(y);
48         memset(ans[0],0,sizeof(ans[0]));
49         for(i=1;i<=kk;i++)
50         {
51             flag=true;
52             split(i,y);
53             for(j=1;j<=n;j++)
54                 if(y[j]>0)
55                 {
56                     y[j]--;
57                     p=merge(y);
58                     for(k=1;k<=n;k++)
59                         ans[i][j]=min(ans[i][j],ans[p][k]+dis[k][j]);
60                     y[j]++;
61                 }
62                 else
63                     flag=false;
64             if(flag)
65                 anss=min(anss,*min_element(ans[i]+1,ans[i]+n+1));
66         }
67         if(anss!=0x3f3f3f3f3f3f3f3f)
68             printf("%lld\n",anss);
69         else
70             printf("-1\n");
71     }
72     return 0;
73 }