从第四个点开始 WA。
也很莫名,感觉算法很对,但代码算下来的结果就是不对。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll
template <class T>
inline void read(T &res)
{
char ch; bool f = 0;
while((ch = getchar()) < '0' || ch > '9') f |= ch == '-';
res = (ch ^ 48);
while((ch = getchar()) <= '9' && ch >= '0') res = (res << 1) + (res << 3) + (ch ^ 48);
res = f ? ~res + 1 : res;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const ll N = 1e5 + 10, M = 4e5 + 10;
ll n, m, k, s, p, qq;
ll ne[M], e[M], w[N], h[N], tot, dis[N];
bool st[N], risk[N], vis[N];
struct node
{
ll id, dis;
bool operator <(const node &x) const
{
return dis > x.dis;
}
};
priority_queue<node> q;
inline void dfs(ll u, ll cnt)
{
if(cnt == s + 1) return ;
if(cnt) vis[u] = 1;
for(rl i=h[u]; ~i; i = ne[i])
{
ll v = e[i];
if(vis[v]) continue;
dfs(v, cnt + 1);
}
}
inline void add(ll a, ll b)
{
ne[++tot] = h[a], h[a] = tot, e[tot] = b;
}
inline void dij()
{
memset(dis, 0x7f, sizeof dis);
memset(st, 0, sizeof st);
dis[1] = 0;
q.push({1, 0});
while(q.size())
{
node asd = q.top();
q.pop();
ll u = asd.id;
if(st[u]) continue;
st[u] = 1;
for(rl i=h[u]; ~i; i = ne[i])
{
ll v = e[i];
if(dis[v] > dis[u] + w[v])
{
dis[v] = dis[u] + w[v];
q.push({v, dis[v]});
}
}
}
}
int main()
{
freopen("1.in", "r", stdin);
memset(h, -1, sizeof h);
read(n), read(m), read(k), read(s);
read(p), read(qq);
for(rl i=1; i <= k; ++ i)
{
ll x;
read(x);
risk[x] = 1;
}
for(rl i=1; i <= m; ++ i)
{
ll a, b;
read(a), read(b);
add(a, b), add(b, a);
}
for(rl i=1; i <= n; ++ i)
if(risk[i]) dfs(i, 0);
for(rl i=1; i <= n; ++ i)
{
if(vis[i]) w[i] = qq;
else w[i] = p;
if(risk[i]) w[i] = 1e18;
}
dij();
write(dis[n] - w[n]);
return 0;
}