记录详细

#include<cstdio>
#include<queue>
#include<algorithm>
const int N = 1e5+7,M = 6e5+7;
const long long INF = 9223372036854775807;
int from[M],to[M],dis[M],nxt[M],head[N],cnt1,cnt2,old_head[N];
int T,n,m,k,in[N];
void add_edge(int f,int t,int d){
	from[++cnt1] = f;
	to[cnt1] = t;
	dis[cnt1] = d;
	nxt[cnt1] = head[f];
	head[f] = cnt1;
}
void add_pedge(int f,int t){
	from[(++cnt2)+m] = f;
	to[m+cnt2] = t;
	nxt[m+cnt2] = head[f];
	head[f] = cnt2+m;
	std::swap(f,t);
	from[(++cnt2)+m] = f;
	to[m+cnt2] = t;
	nxt[m+cnt2] = head[f];
	head[f] = cnt2+m;
}
void init(){
	cnt1 = 0;
	cnt2 = 0;
	for(int i=1;i<=n+2;i++){
		head[i] = 0;
		in[i] = 0;
	}
}
void mid_init(){
	cnt2 = 0;
	for(int i=1;i<=n+2;i++) head[i] = old_head[i];
}
bool been[N];
long long ans[N];
struct Node{
	int num,step;
	Node(){}
	Node(int n,int s){
		num = n;
		step = s;
	}
};
bool operator<(Node a,Node b){
	return a.step>b.step;
}
std::priority_queue<Node> q;
void init_dijkstra(){
	for(int i=1;i<=n+2;i++){
		been[i] = false;
		ans[i] = INF;
	}
	while(q.size()) q.pop();
}
void dijkstra(int s,int e){
	ans[s] = 0;
	q.push(Node(s,0));
	while(q.size()){
		Node mid = q.top();
		q.pop();
		if(mid.num==e) break;
		if(been[mid.num]) continue;
		been[mid.num] = true;
		for(int i=head[mid.num];i;i=nxt[i]){
			if(been[to[i]]) continue;
			if(ans[mid.num]+dis[i]<ans[to[i]]){
				ans[to[i]] = ans[mid.num]+dis[i];
				q.push(Node(to[i],ans[to[i]]));
			}
		}
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		init();
		long long fans=INF;
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1,f,t,d;i<=m;i++){
			scanf("%d%d%d",&f,&t,&d);
			add_edge(f,t,d);
		}
		for(int i=1;i<=n+2;i++) old_head[i] = head[i];
		for(int i=1;i<=k;i++) scanf("%d",&in[i]);
		for(int i=1;i<=k;i<<=1){
//			//debug
//			printf("DEBUG\n");
//			for(int j=1;j<=n+2;j++) printf("%d ",head[j]);
//			putchar('\n');
//			//end debug
			mid_init();
//			//debug
//			for(int j=1;j<=n+2;j++) printf("%d ",head[j]);
//			putchar('\n');
//			//end debug
			for(int j=1;j<=k;j++){
				if((j/i)&1) add_pedge(in[j],n+1);
				else add_pedge(in[j],n+2);
			}
//			for(int j=1;j<=n+2;j++) printf("%d ",head[j]);
//			//debug 
//			putchar('\n');
//			printf("END DEBUG\n");
//			//end debug
			init_dijkstra();
			dijkstra(n+1,n+2);
			fans = std::min(fans,ans[n+2]);
			init_dijkstra();
			dijkstra(n+2,n+1);
			fans = std::min(fans,ans[n+1]);
		}
		printf("%lld\n",fans);
	}
	return 0;
}

额啊啊啊啊啊啊调了3h死活过不了啊啊啊啊QAQ！！