CF8C

Update

同见于我的洛谷博客

思路

看到 ，钦定状压。

用 cost 数组转移，同时用 from 与 way 记录来路，暴力枚举每一种情况。

提交。咋TLE了？

这个算法不够快，还有提升空间。

由于方案任意，可以考虑每次枚举第一个物品时都取编号最小者，时间会有很大优化。然而TLE依旧。

开快读！TLE。

再看看哪里挂了？

涉及到二进制的题，一般不用 math 库中的 log2() 函数（因为其常数贼大），而是手动打 hash 表。

一般这个 hash 表可以利用费马小定理减小空间，见代码。

终于过了。

Code

#include <math.h>
#include <stdio.h>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
inline bol _min(ullt&a,ullt b){return(b<a)?a=b,true:false;}
inline ullt time(int x1,int y1,int x2,int y2){return(llt)(x1-x2)*(x1-x2)+(llt)(y1-y2)*(y1-y2);}
inline uint hash(uint a,uint b){return a*25+b;}
ullt cost[16777220],T[30][30];uint from[16777220],way[16777220];
uint LOG[37];
int X[30],Y[30];
voi get(uint S)
{
    if(!S){putchar('0');return;}
    get(from[S]);
    if(way[S]/25==way[S]%25)printf(" %d 0",way[S]/25+1);else printf(" %d %d 0",way[S]/25+1,way[S]%25+1);
}
int main()
{
    uint n;register uint p,q;
    scanf("%d%d%u",X,Y,&n);for(uint i=1;i<=n;i++)scanf("%d%d",X+i,Y+i);
    for(uint i=0;i<=n;i++)for(uint j=0;j<=n;j++)T[i][j]=time(X[i],Y[i],X[j],Y[j]);
    for(uint i=1;i<=n;i++)for(uint j=1;j<=n;j++)T[i][j]+=T[0][i]+T[j][0];
    const uint tp=1<<n;
    for(uint i=0;i<=30;i++)LOG[(1u<<i)%37]=i;
    for(register uint S=1;S<tp;S++)
    {
        p=S&-S;cost[S]=1145141919810llu;
        for(uint S2=S;S2;S2-=q)
        {
            q=S2&-S2;
            if(_min(cost[S],cost[S^(p|q)]+T[LOG[p%37]+1][LOG[q%37]+1]))
                from[S]=S^(p|q),way[S]=hash(LOG[p%37],LOG[q%37]);
        }
    }
    printf("%llu\n",cost[tp-1]),get(tp-1),putchar('\n');
    return 0;
}