用动态数组来存边,SPFA最短路,求大佬!
#include<bits/stdc++.h>
using namespace std;
int n,m,k,s,p,q,num[100010],x,y,dis[100010];
bool c[100010],d[100010],vis[100010];
struct node{
int q,s;
};
vector<node> a[100010];
queue<int> qt;
void SPFA(int u){
for(int i=0;i<=n;i++){
dis[i]=1e7;
vis[i]=0;
}
dis[u]=0;
vis[u]=1;
qt.push(u);
while(!qt.empty()){
int now=qt.front();
vis[now]=0;
for(int i=0;i<num[now];i++){
if(dis[a[now][i].q]>dis[now]+a[now][i].s){
dis[a[now][i].q]=dis[now]+a[now][i].s;
if(!vis[a[now][i].q]){
vis[a[now][i].q]=1;
qt.push(a[now][i].q);
}
}
}
qt.pop();
}
}
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&k,&s,&p,&q);
while(k--){
scanf("%d",&x);
c[x]=1;
}
while(m--){
scanf("%d%d",&x,&y);
if(c[x]&&c[y]) continue;
if(c[x]) x=0;
if(c[y]) y=0;
a[x].push_back({y,1});
a[y].push_back({x,1});
num[x]++;
num[y]++;
}
SPFA(0);
for(int i=1;i<=n;i++){
if(dis[i]<=s) d[i]=1;
}
for(int i=1;i<=n;i++){
for(int j=0;j<num[i];j++){
if(a[i][j].q==n) a[i][j].s=0;
else if(c[i]||c[a[i][j].q]) a[i][j].s=1e7;
else if(d[i]||d[a[i][j].q]) a[i][j].s=q;
else a[i][j].s=p;
}
}
SPFA(1);
printf("%d",dis[n]);
return 0;
}