ソースコード
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
typedef long long int ll;
using namespace std;
ll N, M, K, S;
ll P, Q;
vector<ll> G[100010];
vector<pair<ll, ll>> G2[100010];
bool F[100010] = {}, R[100010] = {};
priority_queue <pair<ll, ll>>que, _que;
ll d[100010], d2[100010];
int main() {
scanf("%lld%lld%lld%lld%lld%lld", &N, &M, &K, &S, &P, &Q);
for (int i = 0; i <= N; i++) {
d[i] = d2[i] = 1000000000000000000;
}
for (int i = 0; i < K; i++) {
ll C;
scanf("%lld", &C);
G[0].push_back(C);
R[C] = true;
}
for (int i = 0; i < M; i++) {
ll A, B;
scanf("%lld%lld", &A, &B);
G[A].push_back(B);
G[B].push_back(A);
}
d[0] = 0;
que.push(make_pair(-d[0], 0));
while (!que.empty()) {
ll c = -que.top().first, a = que.top().second;
que.pop();
if (c > S) que = _que;
else {
F[a] = true;
for (int i = 0, len = G[a].size(); i < len; i++) {
if (d[G[a][i]] > c + 1) {
d[G[a][i]] = c + 1;
que.push(make_pair(-d[G[a][i]], G[a][i]));
}
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 0, len = G[i].size(); j < len; j++) {
int k = G[i][j];
if (k == N) {
G2[i].push_back(make_pair(0, k));
}
else if (!R[k]) {
G2[i].push_back(make_pair((F[k]) ? Q : P, k));
}
}
}
d2[1] = 0;
que.push(make_pair(-d2[1], 1));
while (!que.empty() && d2[N] == 1000000000000000000) {
ll c = -que.top().first, a = que.top().second;
que.pop();
if (d2[a] > c) continue;
for (int i = 0, len = G2[a].size(); i < len; i++) {
int _a = G2[a][i].second, _b = G2[a][i].first + c;
if (d2[_a] > _b) {
d2[_a] = _b;
que.push(make_pair(-d2[_a], _a));
}
}
}
printf("%lld\n", d2[N]);
}