NOIP2017 D2T2宝藏

考场上写的prim一遍过了大样例也没想什么别的，反例也没举出来。

后来才知道由于要乘上深度所以无法贪心。

正解是状压但我不会，考后一个爆搜碾过去了。

心凉。

 #include<bits/stdc++.h>

 using namespace std;

 int n,m,tmp;long long ans=1e15;

 int inf=1e9+;

 long long f[<<];

 int e[][],d[];

 void dfs(int now)

 {

     if(f[now]>ans)return ;

     if(now==tmp)

     {

         ans=min(ans,f[now]);return;

     }

     for(int i=;i<=n;++i)

     {

         if((now&(<<i-))==)

         for(int j=;j<=n;++j)

         {

             if(now&(<<j-))

             if(e[i][j]!=inf&&f[now|(<<i-)]>f[now]+(d[j]+)*e[i][j])

             {

                 int k=d[i];

                 d[i]=d[j]+;

                 f[now|(<<i-)]=f[now]+d[i]*e[i][j];

                 dfs(now|(<<i-));

                 d[i]=k;

             }

         }

     }

 }

 int main()

 {

     //freopen("1.in","r",stdin);

     //freopen("1.out","w",stdout);

     scanf("%d%d",&n,&m);

     int x,y,w;

     for(int i=;i<=n;++i)

     for(int j=;j<=n;++j)

     e[i][j]=inf;

     for(int i=;i<=m;++i)

     {

         scanf("%d%d%d",&x,&y,&w);

         if(w<e[x][y])

         {

             e[x][y]=e[y][x]=w;

         }

     }

     for(int i=;i<=n;++i)

     {

         memset(f,0x3f,sizeof(f));memset(d,0x3f,sizeof(d));

         tmp=<<n;tmp--;d[i]=;

         f[(<<i-)]=;

         dfs((<<i-));

     }

     printf("%lld",ans);

     return ;

 }