【luogu P3393 逃离僵尸岛】 题解

题目链接：https://www.luogu.org/problemnew/show/P3393

被占领的点可以先连在一个点上然后只需要对这一个点bfs一遍就可以求所有的危险点

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn = 2 * 1e5 + 10;

ll n, m, k, s, val[2], danger[maxn], ddis[maxn], dis[maxn], charge[maxn], v[maxn], u[maxn];

bool vis[maxn], vvis[maxn];

struct edge{

	ll from, to, next, len;

}e[maxn<<2], ee[maxn<<2];

ll cnt, head[maxn], cntt, headd[maxn];

queue<ll> dq, q;

void add(ll u, ll v, ll w)

{

	e[++cnt].from = u;

	e[cnt].len = w;

	e[cnt].next = head[u];

	e[cnt].to = v;

	head[u] = cnt;

}

void ad(ll u, ll v, ll w)

{

	ee[++cntt].from = u;

	ee[cntt].len = w;

	ee[cntt].next = headd[u];

	ee[cntt].to = v;

	headd[u] = cntt;

}

void SPFA()

{

	while(!q.empty())

	{

		ll now = q.front(); q.pop();

		vis[now] = 0;

		for(ll i = head[now]; i != -1; i = e[i].next)

		{

			if(dis[e[i].to] > dis[now] + e[i].len && danger[e[i].to] == 0)

			{

				dis[e[i].to] = dis[now] + e[i].len;

				if(!vis[e[i].to])

				{

					q.push(e[i].to);

					vis[e[i].to] = 1;

				}

			}

		}

	}

}

void BFS()

{

	while(!dq.empty())

	{

		ll now = dq.front(); dq.pop();

		vis[now] = 0;

		for(ll i = headd[now]; i != -1; i = ee[i].next)

		{

			if(ddis[ee[i].to] > ddis[now] + ee[i].len)

			{

				ddis[ee[i].to] = ddis[now] + ee[i].len;

				if(!vvis[ee[i].to])

				{

					dq.push(ee[i].to);

					vvis[ee[i].to] = 1;

				}

			}

		}

	}

}

int main()

{

	memset(head, -1, sizeof(head));

	memset(headd, -1, sizeof(headd));

	memset(dis, 127, sizeof(dis));

	memset(ddis, 127, sizeof(ddis));

	scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&k,&s,&val[0],&val[1]);

	for(ll i = 1; i <= k; i++)

	{

		ll u;

		scanf("%lld",&u);

		danger[u] = 1;

		ad(u, 0, 1);

		ad(0, u, 1);

	}

	for(ll i = 1; i <= m; i++)

	{

		scanf("%lld%lld",&u[i],&v[i]);

		ad(u[i], v[i], 1);

		ad(v[i], u[i], 1);

	}

	dq.push(0), ddis[0] = 0, vvis[0] = 1;

	BFS();

	for(ll i = 1; i <= n; i++)

	if(ddis[i] <= s+1)

	charge[i] = 1;

	for(ll i = 1; i <= m; i++)

	{

		if(danger[u[i]] != 1 && danger[v[i]] != 1)

		{

			add(u[i], v[i], val[charge[v[i]]]);

			add(v[i], u[i], val[charge[u[i]]]);

		}

	}

	q.push(1), dis[1] = 0, vis[1] = 1;

	SPFA();

	/*for(ll i = 0; i <= n; i++)

	cout<<charge[i]<<" ";*/

	printf("%lld",dis[n]-val[charge[n]]);

	return 0;

}