这题一看显然是一个裸的斯坦纳树
我们用$f[i][j]$表示经过的路径中包含了状态$i$所表示的点，且连接了$j$号点的最短路径。
显然，$f[i][j]=min\{f[i$^$k][j]+f[k][j]\}$， 其中$i $&$ k = k$。
转移完毕后，跑一个最短路去更新一遍。
那么显然这题的时间复杂度是$O(2^k\times 最短路时间复杂度)$。
但是这题神TM卡SPFA。。。。
我后来改写了$dij$，再加了个避免重复更新的判断，才过了...
#include<bits/stdc++.h>
#define M 100005
#define L long long
#define INF 1926081719260817LL
using namespace std;
struct edge{int u,v,next;}e[M<<]={}; int head[M]={},use=;
void add(int x,int y,int z){use++;e[use].u=y;e[use].v=z;e[use].next=head[x];head[x]=use;}
L f[<<][M]={};
struct node{
int u; L dis; node(){u=dis=;}
node(int uu,L diss){u=uu; dis=diss;}
friend bool operator <(node a,node b){return a.dis>b.dis;}
}; priority_queue<node> q;
bool vis[M]={};
void spfa(L dfn[]){
memset(vis,,sizeof(vis));
while(!q.empty()){
node uu=q.top(); q.pop();
int u=uu.u;
if(vis[u]) continue; vis[u]=;
for(int i=head[u];i;i=e[i].next)
if(dfn[e[i].u]>dfn[u]+e[i].v){
dfn[e[i].u]=dfn[u]+e[i].v;
q.push(node(e[i].u,dfn[e[i].u]));
}
}
}
int n,m,k,p[]={}; int main(){
scanf("%d%d%d",&n,&k,&m);
for(int i=;i<(<<k);i++)
for(int j=;j<=n;j++) f[i][j]=INF;
for(int i=;i<k;i++){
scanf("%d",p+i);
f[<<i][p[i]]=;
}
for(int i=;i<=m;i++){
int x,y,z; scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
for(int i=;i<(<<k);i++){
for(int j=i;j;j=i&(j-)){
for(int k=;k<=n;k++)
f[i][k]=min(f[i][k],f[j][k]+f[i^j][k]);
}
for(int k=;k<=n;k++)
if(f[i][k]!=INF) q.push(node(k,f[i][k]));
spfa(f[i]);
}
L minn=INF;
for(int i=;i<=n;i++)
minn=min(minn,f[(<<k)-][i]);
cout<<minn<<endl;
}