斯坦纳树的板子题。

斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。

最小生成树是在给定的点集和边中寻求最短网络使所有点连通。

而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。

然而我解决问题并不需要你知道什么关于斯坦纳树的知识。

会状压（子集）DP和最短路就行了。

设dp[s][i]为使s集合中的景点都与点i相连的最小代价。

然后转移有:

\(dp[s][i]=min(dp[s][i],dp[k][i]+dp[s\)^\(k][i])\ (k\subset s)\)

\(dp[s][i]=min(dp[s][i],dp[s][j]+val(i,j))((i,j)\in E)\)

然后第一个转移用子集DP，第二个转移用最短路。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
           using namespace std;#define int long longconst int INF=1e16;const int N=101000;const int M=201000;struct edge{ int to,nxt,w;}e[M*2];int cnt,head[N];void add_edge(int u,int v,int w){ cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt;}struct node{ int id,w; node(int idd=0,int ww=0){ id=idd,w=ww; }};bool operator <(node a,node b){ return a.w>b.w;}priority_queue
          
            q;bool vis[N];void dij(int *dis){ memset(vis,0,sizeof(vis)); while(!q.empty()){ node x=q.top(); q.pop(); int u=x.id; if(vis[u])continue;vis[u]=1; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(dis[v]>dis[u]+e[i].w){ dis[v]=dis[u]+e[i].w; q.push(node(v,dis[v])); } } }}int read(){ int sum=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();} return sum*f;}int n,k,m,dp[50][N],a[10];signed main(){ n=read();k=read();m=read(); for(int i=0;i<(1<