//这道题可以用迪杰特斯拉算法做,但是这道题我用的是SPFA算法,
//记录一下关于链式向前星、spfa算法是怎么操作的,
//spfa算法相比于迪杰特斯拉算法有很多优点,大家可以从网上搜索,很容易找到。
例题链接:https://vjudge.net/problem/HDU-2066
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;
#define inf 0x3f3f3f3f
using namespace std;
const int M=10005;
struct sss
{
int v; //终点
int w; //边的权值
int next;
}a[M<<1];
int head[M]; //head存储的是以i为起点,最后输入的那个编号
int vis[M],ven[M],nums[M]; //SPFS数组,vis记录最短路,ven记录是否在队列,nums记录入队次数
int cnt=0; //链式前向星数组
void add(int u,int v,int w)//链式前向星,加入节点
{
a[cnt].v=v;
a[cnt].w=w;
a[cnt].next=head[u];
head[u]=cnt++;
}
bool SPFA(int s,int n) //从s点开始出发,一共n条边
{
queue <int> q;
memset(vis,inf,sizeof(vis)); //设s点到其余各个点的距离都是最大值
memset(ven,0,sizeof(ven)); //每一个点都不在队列中
memset(nums,0,sizeof(nums));
vis[s]=0; //初始化距离
ven[s]=1; //标记s在队列里面
nums[s]++;//队列次数+1
q.push(s);
while(!q.empty())
{
int x=q.front(); //以x点为翘板
q.pop(); //出队
ven[x]=0; //标记不在队列
for(int i=head[x]; i>=0; i=a[i].next) //遍历与x节点连通的点
{
int y=a[i].v; //y是这条边的终点,以x为翘板,看初始点距离y点的距离可不可以更新
if(vis[y] > vis[x] + a[i].w) //如果 初始点距离终点的距离 > (初始点距离x的距离+i这条边的权值) ——> 更新
{
vis[y] = vis[x] + a[i].w;
if(ven[y]==0) //由于更新了节点,所以后续以这个为基础的最短路,也要更新下,所以如果在队列就不用加入,不在的话加入更新后续节点
{
q.push(y);
ven[y]=1;//标记这个节点在队列中
nums[y]++;//记录加入次数
if(nums[y]>n) return false; //如果这个点加入超过n次,说明存在负圈,直接返回
}
}
}
}
return true;
}
int main()
{
int n,m,t;
int b[M],c[M];
while(cin >> n >> m >> t) //n为边数,m为初始的点的个数,t为目标点的个数
{
cnt=0;
memset(head,-1,sizeof(head)); //链式向前星里面的head数组初始化为-1
for(int i=0;i<n;i++)
{
int x,y,k;
cin >> x >> y >> k;
add(x,y,k);
add(y,x,k); //双向边
}
for(int i=0;i<m;i++) //与草儿家相连的城市,储存在b数组里面(也就是从这个点开始出发,m初始点的个数)
{
cin >> b[i];
}
for(int i=0;i<t;i++) //草儿想去的地方,储存在c数组里面(也就是目的地,t为目标点的个数)
{
cin >> c[i];
}
int minn=inf;
for(int i=0;i<m;i++) //遍历多个找寻最小
{
SPFA(b[i],n);
for(int j=0;j<t;j++)
{
minn=min(minn,vis[c[j]]);
}
}
cout << minn << endl;
}
}