题意：二维平面上有n(n<=100)个点，其中k个是星星(k<=10)，现要构造一棵树，每个星星对应树上的一个叶子结点，求最小花费（总花费为树上所有边的长度（两点间欧几里得距离））
斯坦纳树上的DP问题，只是要求星星必须作为叶子结点，只要在跑第二类转移的时候不让其走到星星点即可。
由于是二维平面，两点间的欧几里得距离就是两点间最短路，连SPFA都不用跑。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef double db; 5 const int N=100+10,inf=0x3f3f3f3f; 6 int n,k; 7 db d[N][N],dp[1<<10][N]; 8 struct P {db x,y;} a[N]; 9 db Dis(P a,P b) {return hypot(a.x-b.x,a.y-b.y);} 10 int main() { 11 scanf("%d%d",&n,&k); 12 for(int i=0; i<n; ++i)scanf("%lf%lf",&a[i].x,&a[i].y); 13 for(int i=0; i<n; ++i) 14 for(int j=0; j<n; ++j) 15 d[i][j]=Dis(a[i],a[j]); 16 memset(dp,100,sizeof dp); 17 for(int i=0; i<k; ++i)dp[1<<i][i]=0; 18 for(int S=1; S<(1<<k); ++S) { 19 for(int S2=(S-1)&S; S2; S2=(S2-1)&S) 20 for(int i=0; i<n; ++i) 21 dp[S][i]=min(dp[S][i],dp[S2][i]+dp[S^S2][i]); 22 for(int i=0; i<n; ++i) 23 for(int j=0; j<n; ++j) 24 if(j>=k)dp[S][j]=min(dp[S][j],dp[S][i]+d[i][j]); 25 } 26 db ans=1e30; 27 for(int i=0; i<n; ++i)ans=min(ans,dp[(1<<k)-1][i]); 28 printf("%.5f\n",ans); 29 return 0; 30 }