「AMPPZ2014」Petrol

传送门：

这是一道bzoj权限题

Luogu团队题链接

解题思路

首先对于每一个点 \(x\) 预处理出 \(nr[x]\) 和 \(dis[x]\)，分别表示离 \(x\) 最近的加油站以及该段距离。

这个过程可以用多源 \(\text{Dijkstra}\) 处理。

然后对于每一条原图中的边 \((u, v, w)\)（\(nr[u]\ne nr[v]\)）

改为这样一条边：\((nr[u], nr[v], dis[u] + dis[v] + w)\)

然后只要离线用并查集维护一下连通性即可。

细节注意事项

最短路不要写挂啊

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#include <queue>

#define rg register

#define pii pair < int, int >

using namespace std;

template < typename T > inline void read(T& s) {

	s = 0; int f = 0; char c = getchar();

	while (!isdigit(c)) f |= (c == '-'), c = getchar();

	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

	s = f ? -s : s;

}

const int _ = 200010;

const int __ = 400010;

int tot, head[_], nxt[__], ver[__], w[__];

inline void Add_edge(int u, int v, int d)

{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v, w[tot] = d; }

int q, n, m, k, c[_], vis[_], dis[_], nr[_];

struct node{ int u, v, d, id; }ask[_], g[__], e[__]; int ans[_];

inline bool cmp(const node& x, const node& y) { return x.d < y.d; }

inline void Dijkstra() {

	static priority_queue < pii > Q;

	memset(dis, 0x3f, sizeof dis);

	for (rg int i = 1; i <= k; ++i)

		Q.push(make_pair(dis[c[i]] = 0, c[i])), nr[c[i]] = c[i];

	while (!Q.empty()) {

		int u = Q.top().second; Q.pop();

		if (vis[u]) continue; vis[u] = 1;

		for (rg int i = head[u]; i; i = nxt[i]) {

			int v = ver[i];

			if (dis[v] > dis[u] + w[i])

				dis[v] = dis[u] + w[i], nr[v] = nr[u], Q.push(make_pair(-dis[v], v));

		}

	}

}

int fa[_];

inline int findd(int x) { return fa[x] == x ? x : fa[x] = findd(fa[x]); }

inline void merge(int x, int y) { fa[findd(x)] = findd(y); }

int main() {

#ifndef ONLINE_JUDGE

	freopen("in.in", "r", stdin);

#endif

	read(n), read(k), read(m);

	for (rg int i = 1; i <= k; ++i) read(c[i]);

	for (rg int u, v, d, i = 1; i <= m; ++i)

		read(u), read(v), read(d), Add_edge(u, v, d), Add_edge(v, u, d), g[i] = (node) { u, v, d };

	Dijkstra();

	int cnt = 0;

	for (rg int u, v, i = 1; i <= m; ++i) {

		u = g[i].u, v = g[i].v;

		if (nr[u] != nr[v]) e[++cnt] = (node) { nr[u], nr[v], dis[u] + dis[v] + g[i].d };

	}

	read(q);

	for (rg int i = 1; i <= q; ++i)

		read(ask[i].u), read(ask[i].v), read(ask[i].d), ask[i].id = i;

	sort(ask + 1, ask + q + 1, cmp);

	sort(e + 1, e + cnt + 1, cmp);

	for (rg int i = 1; i <= n; ++i) fa[i] = i;

	for (rg int i = 1, j = 1; i <= q; ++i) {

		while (j <= cnt && e[j].d <= ask[i].d) merge(e[j].u, e[j].v), ++j;

		ans[ask[i].id] = findd(ask[i].u) == findd(ask[i].v);

	}

	for (rg int i = 1; i <= q; ++i) puts(ans[i] ? "TAK" : "NIE");

	return 0;

}

完结撒花 \(qwq\)

巴特西

「AMPPZ2014」Petrol

解题思路

细节注意事项

参考代码

最新文章

热门文章