最近複習狀壓dp，就突然想起了這道經典題，就再寫一篇今年聯賽的好題。
2. 寶藏
（treasure.cpp/c/pas)
參與考古挖掘的小明得到了一份藏寶圖，藏寶圖上标出了 n 個深埋在地下的寶藏屋， 也給出了這 n 個寶藏屋之間可供開發的 m 條道路和它們的長度。
小明決心親自前往挖掘所有寶藏屋中的寶藏。但是，每個寶藏屋距離地面都很遠，也就是說，從地面打通一條到某個寶藏屋的道路是很困難的，而開發寶藏屋之間的道路則相對容易很多。
小明的決心感動了考古挖掘的贊助商，贊助商決定免費贊助他打通一條從地面到某個寶藏屋的通道，通往哪個寶藏屋則由小明來決定。
在此基礎上，小明還需要考慮如何開鑿寶藏屋之間的道路。已經開鑿出的道路可以任意通行不消耗代價。每開鑿出一條新道路，小明就會與考古隊一起挖掘出由該條道路所能到達的寶藏屋的寶藏。另外，小明不想開發無用道路，即兩個已經被挖掘過的寶藏屋之間的道路無需再開發。
新開發一條道路的代價是：
這條道路的長度 × 從贊助商幫你打通的寶藏屋到這條道路起點的寶藏屋所經過的寶藏屋的數量（包括贊助商幫你打通的寶藏屋和這條道路起點的寶藏屋）。
請你編寫程式為小明標明由贊助商打通的寶藏屋和之後開鑿的道路，使得工程總代價最小，并輸出這個最小值。
【輸入格式】
輸入檔案名為 treasure.in。
第一行兩個用空格分離的正整數 n 和 m，代表寶藏屋的個數和道路數。
接下來 m 行，每行三個用空格分離的正整數，分别是由一條道路連接配接的兩個寶藏屋的編号（編号為 1~n），和這條道路的長度 v。
【輸出格式】
輸出檔案名為 treasure.out。
輸出共一行，一個正整數，表示最小的總代價。
【輸入輸出樣例 1】
treasure.in
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
treasure.out
4
【輸入輸出樣例 1 說明】見選手目錄下的 treasure/treasure1.in 與 treasure/treasure1.ans
小明標明讓贊助商打通了 1 号寶藏屋。小明開發了道路 1->2，挖掘了 2 号寶藏。開發了道路 1->4，挖掘了 4 号寶藏。還開發了道路 4->3，挖掘了 3 号寶藏。工程總代價為：1 × 1 + 1 × 1 + 1 × 2 = 4
(1->2) (1->4) (4->3)
【樣例輸入輸出 2】
treasure.in
4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 2
treasure.out
5
見選手目錄下的treasure/treasure2.in 與 treasure/treasure2.ans。
【輸入輸出樣例 2 說明】
小明標明讓贊助商打通了 1 号寶藏屋。小明開發了道路 1->2，挖掘了 2 号寶藏。開發了道路 1->3，挖掘了 3 号寶藏。還開發了道路 1->4，挖掘了 4 号寶藏。工程總代價為：1 × 1 + 3 × 1 + 1 × 1 = 5
(1->2) (1->3) (1->4)
【輸入輸出樣例 3】
見選手目錄下的 treasure/treasure3.in 和 treasure/treasure3.out。
【資料規模與約定】
對于 20%的資料：
保證輸入是一棵樹，1≤n≤8，v≤5000 且所有的 v 都相等。對于 40%的資料：
1≤n≤8，0≤m≤1000，v≤5000 且所有的v 都相等。對于 70%的資料：
1≤n≤8，0≤m≤1000，v≤ 5000
對 于 100% 的 數 據 ： 1≤n≤12，0≤m≤1000，v≤ 500000
其實看到資料就知道這是一道狀壓了（但是我比較菜，聯賽時狀壓不會寫，随便打了個貪心騙了45分）。用 dp[i]來表示狀态 i 下的最優方案,dis[j]表示 j 到根節點的距離（題目中所描述的 K）用 dfs 來更新答案。（可能有誤，歡迎大家查錯）。
Code：
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000000
#define N 15
using namespace std;
int dist[N][N],dis[N],flag[N][N],dp[1<<13],n,m;
inline int read()
{
int f=1,x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
return x;
}
void dfs(int x)
{
for(int i=1;i<=n;i++)
if((1<<(i-1))&x)
for(int j=1;j<=n;j++)
if(!(1<<(j-1)&x)&&flag[i][j])
if(dp[1<<(j-1)|x]>dp[x]+dis[i]*dist[i][j])
{
int t=dis[j];
dis[j]=dis[i]+1;
dp[1<<(j-1)|x]=dp[x]+dis[i]*dist[i][j];
dfs(1<<(j-1)|x);
dis[j]=t;
}
}
int main()
{
n=read(),m=read();
int ans=inf;
memset(dist,0x3f,sizeof(dist));
for(int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
flag[x][y]=1;flag[y][x]=1;
dist[x][y]=min(dist[x][y],z);
dist[y][x]=min(dist[y][x],z);
}
for(int i=1;i<=n;i++)
{
memset(dis,0x3f,sizeof(dis));
memset(dp,0x3f,sizeof(dp));
dis[i]=1;dp[1<<(i-1)]=0;
dfs(1<<(i-1));
ans=min(ans,dp[(1<<n)-1]);
}
printf("%d",ans);
return 0;
}