[NOIP2017]宝藏

题目（洛谷）
这题看数据范围：状压dp，没跑了。
可是怎么dp呢？
这题比去年《愤怒的小鸟》一题要难，毕竟去年的状压dp是试水题。
然后今年就不水了，呵(f**k)呵(off)。
其实这题仅需一维的状压即可，
用dp[st]表示当前状态的最小花费。
很明显，这题的最小花费求出来一定是一棵树。
然后以每个点做一遍dp，复杂度O(n^3)，接近O(n^4)。
注意：这个dp过程是记忆化搜索......

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <climits>
#define readf(f) scanf("%lf",&f)
#define llmax LONG_LONG_MAX
#define llmin LONG_LONG_MIN
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
template <class _E> inline void read(_E &e)
{
    e=0;bool ck=0;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
    while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
    if(ck)e=-e;
}
int a[15][15],dis[15];
int dp[(1<<12)+5];
int all,n,m;
int id[15];
int ans=INT_MAX;
void dfs(int nowst)
{
    for (int i=1;i<=n;++i)
    {
        if (nowst&id[i])
        {
            for (int j=1;j<=n;++j)
            {
                if (a[i][j]<inf && !(nowst&id[j]))
                {
                    if (dp[nowst|id[j]]>dp[nowst]+dis[i]*a[i][j])
                    {
                        dp[nowst|id[j]]=dp[nowst]+dis[i]*a[i][j];
                        int tmp=dis[j];
                        dis[j]=dis[i]+1;
                        dfs(nowst|id[j]);
                        dis[j]=tmp;
                    }
                }
            }
        }
    }
}
int main()
{
    read(n),read(m);
    memset(a,inf,sizeof a);
    all=(1<<n)-1;
    id[1]=1;
    for (int i=2;i<=n;++i) id[i]=(id[i-1]<<1);
    for (int i=1;i<=m;++i)
    {
        int x,y,z;
        read(x),read(y),read(z);
        if (a[x][y]>z) a[x][y]=a[y][x]=z;
    }
    for (int d=1;d<=n;++d)
    {
        memset(dis,inf,sizeof dis);
        memset(dp,inf,sizeof dp);
        dp[id[d]]=0,dis[d]=1;
        dfs(id[d]);
        ans=min(ans,dp[all]);
    }
    cout<<ans;
    return 0;
}