#include<cstdio>
#include<queue>
#include<cstring>
#define nn 100010
#define pii pair<ll,int>
#define mk make_pair
#define x first
#define y second
using namespace std;
/*struct node{
int x,y;
bool operator <(const node&b)const{
return x>b.x;
}
};
priority_queue<node>QQ;多种*/
//priority_queue<int,vector<int>,less<int> >Q;//单个排序;
typedef int ll;
struct node{int end,next,s;
}g[nn*4];
priority_queue<pii>Q;//pair
int n,m,u,t,tot,j,c,k,i,z,x,y;
int fa[nn],blink[nn];
int dis[nn][32],ans;
int min(int a,ll b){return (a>b)?b:a;}
void DJ()
{pii z;
while (!Q.empty()){
z=Q.top();Q.pop();
for (int i=fa[z.y];i;i=g[i].next)
{int u=g[i].end;
if (dis[u][t]>z.x*-1+g[i].s&&(z.x*-1+g[i].s>0))
{dis[u][t]=z.x*-1+g[i].s;
Q.push(mk(dis[u][t]*-1,u));
}
}
}
}
void add(int a,int b,int c)
{g[++tot].end=b;g[tot].next=fa[a];
g[tot].s=c;fa[a]=tot;
}
int main()
{
freopen("bst.in","r",stdin);
freopen("bst.out","w",stdout);
scanf("%d%d%d%d",&n,&m,&c,&k);
for (i=1;i<=k;i++)scanf("%d",&blink[i]);
while (m--){scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
memset(dis,0x7f,sizeof(dis));
dis[1][0]=0;t=0;
Q.push(mk(0,1));
DJ();
while (c--){
for (i=1;i<=k;i++){
x=blink[i];
for (j=fa[x];j;j=g[j].next)
{u=g[j].end;
if (dis[x][t]<dis[u][t+1])
dis[u][t+1]=dis[x][t],Q.push(mk(dis[u][t+1]*-1,u));
}
}
t++;
DJ();
}
ans=0x7fffffff;
for (i=0;i<=t;i++)ans=min(ans,dis[n][i]);
printf("%d\n",ans);
return 0;
}
评论