1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
struct {
int to,next,dis;
}e[499999];
inline int read(){
int x=0,w=0;char ch=getchar();
while (!isdigit(ch))w|=ch=='-',ch=getchar();
while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return w?-x:x;
}
int cnt,head[400000],dis[300000],inque[300000],tag[300000];
inline void add(int u,int v,int d){
e[++cnt].to=v;
e[cnt].dis=d;
e[cnt].next=head[u];
head[u]=cnt;
}
void spfa(int s){
memset(dis,0x3f,sizeof(dis));
memset(inque,0,sizeof(inque));
dis[s]=0;queue<int>q;q.push(s);
while (!q.empty()){
int u=q.front();q.pop();inque[u]=0;
for (int i=head[u];i;i=e[i].next){
int v=e[i].to;
if (dis[v]>dis[u]+e[i].dis){
dis[v]=dis[u]+e[i].dis;
if (!inque[v]){
inque[v]=1;q.push(v);
}
}
}
}
}
signed main(){
int n=read(),m=read(),k=read(),s=read(),p=read(),q=read();
for (int i=1;i<=k;++i){
int t=read();
tag[t]=2;
add(0,t,0);
}
for (int i=1;i<=m;++i){
int u=read(),v=read();
add(u,v,1);add(v,u,1);
}
spfa(0);
for (int i=1;i<=n;++i)
tag[i]=tag[i]==0?dis[i]<=s:2;
for (int i=1;i<=cnt;++i){
if (tag[e[i].to]==2){e[i].dis=inf;continue;}
if (e[i].to==n||e[i].to==1){e[i].dis=0;continue;}
if (tag[e[i].to]==1){e[i].dis=q;continue;}
else e[i].dis=p;
}
spfa(1);
printf("%lld",dis[n]);
return 0;
}
|
近期评论