[LUOGU] 3959 宝藏

https://www.luogu.org/problemnew/show/P3959

注意到n非常小，考虑状压/搜索。

发现状压需要枚举起点，跑n次，一个问题是转移不可以以数字大小为阶段了，考虑用dfs的方式递推。

一开始的naive想法是，跑2^n次Floyd，处理出每种联通情况下到根的最少经过点数，然后由N-1状态开始倒着记忆化搜索，出了很多锅，细节也不少。

考虑正着做，即刷表，发现很好写！也不必跑Floyd了，用dis数组一边跑一边更新最短距离就行。

f[S]表示联通情况为s时的最小代价，转移时枚举一个集合内的点，由它向外枚举一个点转移。

#include<iostream>
#include<cstdio>

using namespace std;

inline int rd(){
    int ret=0,f=1;char c;
    while(c=getchar(),!isdigit(c))f=c=='-'?-1:1;
    while(isdigit(c))ret=ret*10+c-'0',c=getchar();
    return ret*f;
}

const int MAXN=13;
const int INF=1<<29;

int n,m,N;

int a[MAXN][MAXN];
int f[1<<MAXN],dis[1<<MAXN];

void dp(int s){
    for(int i=1;i<=n;i++){
        if(!(s&(1<<(i-1)))) continue;
        for(int j=1;j<=n;j++){
            if(s&(1<<(j-1))) continue;
            if(a[i][j]==INF) continue;
            if(f[s|(1<<(j-1))]>f[s]+(dis[i]+1)*a[i][j]){
                int sav=dis[j];
                dis[j]=dis[i]+1;
                f[s|(1<<(j-1))]=f[s]+(dis[i]+1)*a[i][j];
                dp(s|(1<<(j-1)));
                dis[j]--;
            }
        }
    }
}

int main(){
    n=rd();m=rd();N=1<<n;
    int x,y,w;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=INF;
    for(int i=1;i<=m;i++){
        x=rd();y=rd();w=rd();
        a[y][x]=a[x][y]=min(a[x][y],w);
    }
    int ans=INF;
    for(int i=1;i<=n;i++){
        for(int j=0;j<N;j++) f[j]=INF;
        for(int j=1;j<=n;j++) dis[j]=INF;
        f[0]=0;f[1<<(i-1)]=0;dis[i]=0;
        dp(1<<(i-1));
        ans=min(ans,f[N-1]);
    }
    cout<<ans;
    return 0;
}