2016-yo-t5-source.cpp

#include <bits/stdc++.h>
#define INF (1LL<<61)
#define int long long

using namespace std;

typedef pair<int, int> pii;

struct edge {
  int to, cost;
  edge(){}
  edge(int pto, int pcost) {
    to = pto; cost = pcost;
  }
};

int n, m, k, s, p, q, town[100005], c[100005], d[100005];
vector<edge> g[100005];
vector<int> tg[100005];

int dijkstra() {
  fill(d, d + n + 1, INF);

  priority_queue<pii, vector<pii>, greater<pii>> qu;
  d[1] = 0;
  qu.push(pii(0, 1));

  while(qu.size()) {
    pii p = qu.top();
    qu.pop();
    int v = p.second;
    if (d[v] < p.first) continue;
    for (int i = 0; i < g[v].size(); ++i) {
      edge e = g[v][i];
      if (d[e.to] <= d[v] + e.cost) continue;
      d[e.to] = d[v] + e.cost;
      qu.push(pii(d[e.to], e.to));
    }
  }

  return d[n];
}

void checkDanger() {
  for (int i = 0; i < k; ++i) {
    int temp[100005] = {0};
    queue<pii> qu;
    qu.push(pii(c[i], 0));

    while (qu.size()) {
      pii t = qu.front();
      qu.pop();
      if ((s < t.second) || (temp[t.first] == 1)) continue;

      if (town[t.first] != 2)
	temp[t.first] = 1;
      for (int j = 0; j < tg[t.first].size(); ++j) {
	if (town[tg[t.first][j]] == 2) continue;
	qu.push(pii(tg[t.first][j], t.second + 1));
      }
    }

    for (int j = 1; j <= n; ++j)
      town[j] = max(town[j], temp[j]);
  }
}
  

signed main() {
  cin >> n >> m >> k >> s >> p >> q;

  for (int i = 0; i < k; ++i) {
    int temp;
    cin >> temp;
    town[temp] = 2;
    c[i] = temp;
  }

  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    tg[a].push_back(b);
    tg[b].push_back(a);
  }

  checkDanger();

  for (int i = 1; i <= n; ++i) {
    if (town[i] == 2) continue;
    for (int j = 0; j < tg[i].size(); ++j) {
      int state = town[tg[i][j]], cost;
      if (state == 2) continue;
      cost = (tg[i][j] == n) ? 0 : (state == 0) ? p : q;
      g[i].push_back(edge(tg[i][j], cost));
    }
  }

  cout << dijkstra() << endl;
  
  return 0;
}