「AMPPZ2014」The Captain

传送门：

这是一道bzoj权限题

Luogu团队题链接

解题思路

直接连边的话边数肯定会爆炸，考虑减少边数。

我们画出坐标系，发现一个东西：

对于两个点 \(A,B\)，\(|x_A-y_A|\) 可以经由由他们俩之间的若干点取到，\(y\) 同理。

所以我们只需要先把所有点分别按照 \(x\) 和 \(y\)，相邻两点之间连边即可。

细节注意事项

不要写挂最短路

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#include <queue>

#define rg register

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;

}

typedef long long LL;

const int _ = 200010;

const int __ = 800010;

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; }

inline void link(int u, int v, int d) { Add_edge(u, v, d), Add_edge(v, u, d); }

int n, vis[_]; LL dis[_];

struct node { int x, y, id; }p[_];

inline bool cmp1(const node& a, const node& b) { return a.x < b.x; }

inline bool cmp2(const node& a, const node& b) { return a.y < b.y; }

inline void Dijkstra() {

	priority_queue < pair < LL, int > > Q;

	memset(dis, 0x3f, sizeof dis);

	dis[1] = 0, Q.push(make_pair(0, 1));

	while (!Q.empty()) {

		pair < LL, int > x = Q.top(); Q.pop();

		int u = x.second;

		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], Q.push(make_pair(-dis[v], v));

		}

	}

}

int main() {

#ifndef ONLINE_JUDGE

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

#endif

	read(n);

	for (rg int i = 1; i <= n; ++i) read(p[i].x), read(p[i].y), p[i].id = i;

	sort(p + 1, p + n + 1, cmp1);

	for (rg int i = 1; i < n; ++i) link(p[i].id, p[i + 1].id, p[i + 1].x - p[i].x);

	sort(p + 1, p + n + 1, cmp2);

	for (rg int i = 1; i < n; ++i) link(p[i].id, p[i + 1].id, p[i + 1].y - p[i].y);

	Dijkstra();

	printf("%lld\n", dis[n]);

	return 0;

}

完结撒花 \(qwq\)

巴特西

「AMPPZ2014」The Captain

解题思路

细节注意事项

参考代码

最新文章

热门文章