记录编号	290086	评测结果	AAAAAAAAAA
题目名称	[省常中2011S4] starhder的旅游	最终得分	100
用户昵称	派特三石	是否通过	通过
代码语言	C++	运行时间	0.112 s
提交时间	2016-08-05 19:58:24	内存使用	79.64 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=210,maxe=201000;
struct edge
{
	int from,to,dis,next;
}e[maxe];
struct node
{
	int num,dis;
	node(int a,int b)
	{
		num=a;dis=b;
	}
	bool operator <(const node&a)const
	{
		return dis>a.dis;
	}
};
int n,m,kk,len,head[maxn],dis[maxn][maxn],vis,full,f[12][1<<21],bi[15];
void insert(int x,int y,int z)
{
	len++;e[len].from=x;e[len].to=y;e[len].dis=z;e[len].next=head[x];head[x]=len;
}
void dj(int x)
{
	memset(dis[x],127,sizeof(dis[x]));
	priority_queue<node> q;q.push(node(x,0));
	bool ff[maxn]={0};dis[x][x]=0;
	while(!q.empty())
	{
		node tem=q.top();q.pop();int k=tem.num;ff[k]=1;
		for(int i=head[k];i;i=e[i].next)
		{
			int j=e[i].to;
			if(!ff[j]&&dis[x][j]>dis[x][k]+e[i].dis)
			{
				dis[x][j]=dis[x][k]+e[i].dis;
				q.push(node(j,dis[x][j]));
			}
		}
	}
}
int dp(int x,int vis)
{
//	cout<<x<<' '<<vis<<' '<<full<<endl;
	if(vis==full)return dis[bi[x]][n];
	if(f[x][vis])return f[x][vis];
	f[x][vis]=0x7fffffff;
	for(int i=1;i<=kk+1;++i)
	{
		if((vis&1<<i)==0){
	
			f[x][vis]=min(f[x][vis],dp(i,vis|1<<i)+dis[bi[x]][bi[i]]);
		}
	}
//	cout<<f[x][vis]<<endl;
	return f[x][vis];
}
int main()
{
	freopen("starhder.in","r",stdin);
	freopen("starhder.out","w",stdout);
	scanf("%d%d%d",&n,&m,&kk);full|=1<<1;bi[1]=1;
	for(int i=2;i<=kk+1;++i){
		int x;scanf("%d",&x);bi[i]=x;
		full|=1<<i;
	}
	for(int i=1;i<=m;++i)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		insert(x,y,z);insert(y,x,z);
	}
	for(int i=1;i<=kk+1;++i)dj(bi[i]);
	printf("%d\n",dp(1,0));
	fclose(stdin);
	fclose(stdout);
	return 0;
}