RT

这里是代码

#include<bits/stdc++.h>
using namespace std;
const int N=501;
struct node{int value,pos;};
struct point{
	int nxt,to,val;
}e[N<<1];
bool operator <(node a,node b){return a.value<b.value;}
priority_queue<node>q;
int f[N][1<<12],n,m,k,u,v,w,head[N],cnt=0,Key[12];
bool vis[12];
void add(int u,int v,int w){
	e[++cnt].nxt=head[u];
	head[u]=cnt;
	e[cnt].to=v;
	e[cnt].val=w;
}
void dijkstra(int sta){
	memset(vis,0,sizeof vis);
	while(!q.empty()){
		node p=q.top();q.pop();
		int x=p.pos;
		if(vis[x])continue;vis[x]=true;
		for(int i=head[x];i;i=e[i].nxt){
			int v=e[i].to;
			if(f[v][sta]>f[x][sta]+e[i].val){
				f[v][sta]=f[x][sta]+e[i].val;
				q.push((node){f[v][sta],v});
			}
		}
	}
}
int main(){
	memset(f,0x3f,sizeof f);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w),add(v,u,w);
	}
	for(int i=1;i<=k;i++){
		scanf("%d",&Key[i]);
		f[Key[i]][1<<(i-1)]=0;
	}
	for(int sta=1;sta<=(1<<k)-1;sta++){
//		puts("OK");
		for(int i=1;i<=n;i++){
			for(int subs=sta&(sta-1);subs;subs=sta&(subs-1))
				f[i][sta]=min(f[i][sta],f[i][subs]+f[i][sta^subs]);
			if(f[i][sta]!=0x3f)q.push((node){f[i][sta],i});
		}
		dijkstra(sta);
	}
	int ans=2e9;
	for(int i=1;i<=n;i++)
	ans=min(ans,f[i][(1<<k)-1]);
	printf("%d\n",ans);
	return 0;
}