C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=2020,M=2e5+10;
int h[N],e[M],ne[M],w[N],target[M],idx;
int st[N],dist[N],q[N];
int n,m,k,t;
void add(int a,int b,int c)
{
e[idx]=b,target[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void spfa()
{
int hh=0,tt=0;
for(int i=1;i<=n;i++)
if(dist[i]==0)
{
st[i]=true;
q[tt++]=i;
if(tt==N) tt=0;
}
while(hh!=tt)
{
auto&x=q[hh++];
st[x]=false;
if(hh==N) hh=0;
for(int i=h[x];~i;i=ne[i])
{
int y=e[i],z=target[i];
if(dist[z]>max(dist[x],dist[y])+max(w[x],w[y]))
{
dist[z]=max(dist[x],dist[y])+max(w[x],w[y]);
if(!st[z])
{
st[z]=true;
q[tt++]=z;
if(tt==N) tt=0;
}
}
}
}
}
int main()
{
cin>>n>>m>>k>>t;
for(int i=1;i<=n;i++) cin>>w[i];
memset(h,-1,sizeof h);
memset(dist,0x3f,sizeof dist);
while(m--)
{
int x;cin>>x;
dist[x]=0;
}
while(k--)
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
spfa();
cout<<dist[t]<<endl;
return 0;
}