题目链接：Fire-Fighting Hero

大意：给出多个点，问这些点，到所有点的最短路当中的最大值是多少。和一个单独的点到所有点的最短路的最大值除C之后比较，输出最小的最大值。

我们肯定不能以每一个点去跑最短路，我们分析可知，因为从每个点出发是一样的，所以我们可以单独建立一个点，指向这些点，路程为0，最后跑这个点到所有点的最短路。单独的点就直接跑最短路即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010,M=1000010;
int T,n,m,s,k,c,st,d[N],vis[N];
int head[N],nex[M],to[M],w[M],tot;
inline void add(int a,int b,int c){
	to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
int dijkstra(int x){
	memset(d,0x3f,sizeof d);	d[x]=0;	memset(vis,0,sizeof vis);
	priority_queue<pair<int,int> > q;	q.push({0,x});
	while(q.size()){
		int u=q.top().second;	q.pop();	
		if(vis[u])	continue;	vis[u]=1;
		for(int i=head[u];i;i=nex[i]){
			if(d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];	q.push({-d[to[i]],to[i]});
			}
		}
	}	int mx=0;
	for(int i=1;i<=n;i++)	if(d[i]!=0x3f3f3f3f3f3f3f3f)mx=max(mx,d[i]);
	return mx;
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		tot=0;	memset(head,0,sizeof head);
		scanf("%lld %lld %lld %lld %lld",&n,&m,&s,&k,&c);	st=n+1;
		for(int i=1;i<=k;i++){
			int x;	scanf("%lld",&x);	add(st,x,0);
		}
		while(m--){
			int a,b,c;	scanf("%lld %lld %lld",&a,&b,&c);
			add(a,b,c);	add(b,a,c);
		}
		int res1=dijkstra(st);	int res2=dijkstra(s);
		if(res2<=res1*c)	printf("%lld\n",res2);
		else	printf("%lld\n",res1);
	}
	return 0;
}