应该没错的思路:
1.先建用链式前向星存一张不带边权的图,用来bfs求被感染的城市。补充一下:1表示有危险的,0表示安全的,-1表示沦陷的。
2.再建一张带边权的图,边权计算的话得继续分类讨论
情况1:起点或终点中有一个为已经沦陷的城市就不建这条边
情况2:如果该边连接n节点,则只建u->v且边权为0的边
情况3:终点城市已经有危险,则建u->v且边权为Q,如果没危险就边权为P(起点同理)
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, k, s, c[N], P, Q;
int nxtj[N << 2], headj[N << 2], toj[N << 2], cnttj;
inline void addj(int u, int v)
{
nxtj[++cnttj] = headj[u];
headj[u] = cnttj;
toj[cnttj] = v;
}
struct nodew
{
int u;
int step;
};
queue<nodew> qj;
int safe[N];
int xx[N << 2], yy[N << 2];
bool visi[N];
void bfs(int ss)
{
qj.push({ss, 0});
while (!qj.empty())
{
int u = qj.front().u, ste = qj.front().step;
qj.pop();
// if ( u == n)
// continue;
if (ste == s)
continue;
for (int i = headj[u]; i; i = nxtj[i])
{
int v = toj[i];
if (visi[v])
continue;
visi[v] = true;
safe[v] = 1;
qj.push({v, ste + 1});
}
}
}
struct node
{
int u;
long long dis;
bool operator<(const node &a) const
{
return dis > a.dis;
}
};
int nxt[N << 2], head[N << 2], to[N << 2], va[N << 2], cntt;
inline void add(int u, int v, int val)
{
nxt[++cntt] = head[u];
head[u] = cntt;
to[cntt] = v;
va[cntt] = val;
}
long long dis[N];
bool vis[N];
priority_queue<node> q;
void dijkstra()
{
q.push({1, 0});
while (!q.empty())
{
int u = q.top().u;
q.pop();
if (vis[u])
continue;
vis[u] = true;
for (int i = head[u]; i; i = nxt[i])
{
int v = to[i], vanow = va[i];
if (dis[v] > dis[u] + vanow * 1ll)
{
dis[v] = dis[u] + vanow * 1ll;
q.push({v, dis[v]});
}
}
}
}
int main()
{
// ios::sync_with_stdio(0);
// cin.tie(0), cout.tie(0);
memset(dis,0x3f, sizeof dis);
cin >> n >> m >> k >> s;
cin >> P >> Q;
for (int i = 1; i <= k; i++)
cin >> c[i];
for (int i = 1; i <= m; i++)
{
cin >> xx[i] >> yy[i];
addj(xx[i], yy[i]);
addj(yy[i], xx[i]);
if (xx[i] > yy[i])
swap(xx[i], yy[i]);
}
for (int i = 1; i <= k; i++)
{
visi[c[i]] = true;
safe[c[i]] = -1;
bfs(c[i]);
}
for (int i = 1; i <= m; i++)
{
if (safe[yy[i]] == -1 || safe[xx[i]] == -1)
continue;
if (yy[i] == n)
add(xx[i], yy[i], 0);
if (safe[yy[i]] == 1)
add(xx[i], yy[i], Q);
else if (safe[yy[i]] == 0)
add(xx[i], yy[i], P);
if (safe[xx[i]] == 1)
add(yy[i], xx[i], Q);
else if (safe[xx[i]] == 0)
add(yy[i], xx[i], P);
}
dis[1] = 0;
dijkstra();
cout << dis[n];
return 0;
}