bzoj4489 [Jsoi2015]地铁线路最短路

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=4489

题解

感觉又被骗了。看这道题的 AC 人数不多，以为是一道很好的题目。结果发现是一个非常一般的最短路啊。

第一问的话，相当于同一个集合内的点可以瞬移，不需要花钱。于是可以每条线路建一个点，把每个站点向所在线路连边，边权为 \(0\)；每条道路向站点连边，边权为 \(1\)。显然从 \(S\) 到 \(T\) 的最短路就是第一问的答案。最短路可以通过 01bfs 实现。

然后第二问的话，也可以继续建图来做。但是有一个更方便的做法。我们可以通过第一问得到的最短路给每一条线路和每个站点分层。然后对于同一层，枚举每一条线路，用这条线路上低一层的点来更新本层的点。（更新可以通过前后缀最大值来实现）

代码如下。

#include<bits/stdc++.h>

#include<tr1/unordered_map>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b , 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b , 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I>

inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

const int N = 3e5 + 50000 + 7;

const int M = 3e5 + 7;

const int INF = 0x3f3f3f3f;

int n, m, nod, S, T, hd, tl;

int dis[N], p[N], mxt[N], mxt2[N], pre[N], suf[N];

std::deque<int> q;

std::tr1::unordered_map<std::string, int> mp;

std::vector<int> v[N];

char tmp[50];

struct Edge { int to, ne; } g[N * 6]; int head[N], tot;

inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; }

inline void adde(int x, int y) { addedge(x, y), addedge(y, x); }

inline void build() {

	for (int i = 1; i <= n; ++i) {

		int len = v[i].size();

		for (int j = 0; j < len; ++j) adde(i + m, v[i][j]);

	}

}

inline void bfs() {

	q.push_back(S);

	memset(dis, -1, sizeof(dis)), dis[S] = 0;

	while (!q.empty()) {

		int x = q.front(); q.pop_front();

		if (x <= m) {

			for fec(i, x, y) if (!~dis[y]) dis[y] = dis[x] + 1, q.push_back(y);

		} else for fec(i, x, y) if (!~dis[y]) dis[y] = dis[x], q.push_front(y);

	}

}

inline bool cmp(const int &x, const int &y) { return dis[x + m] < dis[y + m]; }

inline void work() {

	build();

	bfs();

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

	std::sort(p + 1, p + n + 1, cmp);

	int r = 0;

	while (r < n && dis[p[r + 1] + m] <= 0) ++r;

	for (int i = 1; i <= n; ++i) {

		int l = r + 1;

		while (r < n && dis[p[r + 1] + m] == i) ++r;

		for (int j = l; j <= r; ++j) {

			int id = p[j], len = v[id].size();

			pre[0] = suf[len + 1] = -INF;

			for (int k = 0; k < len; ++k) pre[k + 1] = std::max(pre[k] + 1, dis[v[id][k]] == i - 1 ? mxt[v[id][k]] : -INF);

			for (int k = len - 1; ~k; --k) suf[k + 1] = std::max(suf[k + 2] + 1, dis[v[id][k]] == i - 1 ? mxt[v[id][k]] : -INF);

			for (int k = 0; k < len; ++k) if (dis[v[id][k]] == i) smax(mxt[v[id][k]], std::max(pre[k + 1], suf[k + 1]));

		}

	}

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

	printf("%d\n", mxt[T]);

}

inline void init() {

	read(n), read(m);

	for (int i = 1; i <= m; ++i) scanf("%s", tmp), mp[tmp] = i;

	for (int i = 1; i <= n; ++i) {

		int l;

		read(l);

		while (l--) scanf("%s", tmp), v[i].pb(mp[tmp]);

	}

	scanf("%s", tmp), S = mp[tmp];

	scanf("%s", tmp), T = mp[tmp];

}

int main() {

#ifdef hzhkk

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

#endif

	init();

	work();

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

bzoj4489 [Jsoi2015]地铁线路最短路

题目传送门

题解

最新文章

热门文章

巴特西

bzoj4489 [Jsoi2015]地铁线路 最短路

题目传送门

题解

最新文章

热门文章

bzoj4489 [Jsoi2015]地铁线路最短路