[题解] 洛谷 P3393 逃离僵尸岛

很明显是一个最短路，但是如何建图才是关键。

对于每一个不可遍历到的点，可以向外扩散，找到危险城市。

若是对于每一个这样的城市进行搜索，时间复杂度就为\(O(n^2)\)，显然过不了。不妨把它们放在一个BFS里面进行搜索，先遍历可以向外延伸最长的点，因为这个点是可以存活很长的。若之后再遍历到这个点的时候，就不用在遍历了，因为这时候的存活时间已经没有之前遍历的时候高了。BFS+打标记遍历完一张图只需要\(O(n)\)的时间复杂度，很大程度上优化了建图方面。

最后根据所给的边跑一遍最短路即可，代码如下：

#include <queue>

#include <cstdio>

#include <vector>

#include <cstring>

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f

void Quick_Read(LL &N) {

	N = 0;

	char c = getchar();

	LL op = 1;

	while(c < '0' || c > '9') {

		if(c == '-')

			op = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		N = (N << 1) + (N << 3) + c - 48;

		c = getchar();

	}

	N *= op;

}

const LL MAXN = 1e6 + 5;

struct Node {

	LL to, dist;

	Node() {}

	Node(LL T, LL D) {

		to = T;

		dist = D;

	}

	friend bool operator > (Node x, Node y) {

		return x.dist > y.dist;

	}

};

struct Flee {

	LL step, id;

	Flee() {}

	Flee(LL I, LL S) {

		step = S;

		id = I;

	}

	friend bool operator > (Flee x, Flee y) {

		return x.step < y.step;

	}

};

vector<LL> v[MAXN];

vector<Node> wg[MAXN];

queue<Flee> que;

priority_queue<Node, vector<Node>, greater<Node> > qu;

bool f[MAXN], vis[MAXN], vi[MAXN], V[MAXN];

LL c[MAXN], w[MAXN];

LL A[MAXN], B[MAXN], d[MAXN];

LL n, m, k, s, p, q;

void Dijkstra() {

	memset(d, 0x3f, sizeof(d));

	qu.push(Node(1, 0));

	d[1] = 0;

	while(!qu.empty()) {

		LL now = qu.top().to; qu.pop();

		if(V[now])

			continue;

		V[now] = true;

		LL SIZ = wg[now].size();

		for(LL i = 0; i < SIZ; i++) {

			LL next = wg[now][i].to;

			if(d[now] + wg[now][i].dist < d[next]) {

				d[next] = d[now] + wg[now][i].dist;

				qu.push(Node(next, d[next]));

			}

		}

	}

	printf("%lld", d[n]);

}

void bfs() {

	for(LL i = 1; i <= k; i++) {

		que.push(Flee(c[i], s));

		vi[c[i]] = 1;

	}

	while(!que.empty()) {

		Flee now = que.front(); que.pop();

		if(vis[now.id])

			continue;

		vis[now.id] = 1;

		vi[now.id] = 1;

		if(now.step == 0)

			continue;

		LL SIZ = v[now.id].size();

		for(LL i = 0; i < SIZ; i++) {

			LL nex = v[now.id][i];

			que.push(Flee(nex, now.step - 1));

		}

	}

}

void Read() {

	Quick_Read(n);

	Quick_Read(m);

	Quick_Read(k);

	Quick_Read(s);

	Quick_Read(p);

	Quick_Read(q);

	for(LL i = 1; i <= k; i++) {

		Quick_Read(c[i]);

		f[c[i]] = true;

	}

	for(LL i = 1; i <= m; i++) {

		Quick_Read(A[i]);

		Quick_Read(B[i]);

		v[A[i]].push_back(B[i]);

		v[B[i]].push_back(A[i]);

	}

}

void Build() {

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

		w[i] = p;

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

		if(vi[i])

			w[i] = q;

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

		w[c[i]] = INF;

	for(LL i = 1; i <= m; i++) {

		if(B[i] == n) {

			wg[A[i]].push_back(Node(B[i], 0));

			wg[B[i]].push_back(Node(A[i], w[A[i]]));

		}

		else if(A[i] == n) {

			wg[A[i]].push_back(Node(B[i], w[B[i]]));

			wg[B[i]].push_back(Node(A[i], 0));

		}

		else {

			wg[A[i]].push_back(Node(B[i], w[B[i]]));

			wg[B[i]].push_back(Node(A[i], w[A[i]]));

		}

	}

}

int main() {

	Read();

	bfs();

	Build();

	Dijkstra();

	return 0;

}

巴特西

[题解] 洛谷 P3393 逃离僵尸岛

最新文章

热门文章