P3556 题解

标签：int 题解 路径 P3556 长度 include inque dis

前言

题目传送门！

更好的阅读体验？

最短路应用。内容抄自某校课件。

思路

首先想到题目与最短路有关。

假如 \(a\) 到 \(b\) 的最短路径长度是 \(x\)，那么对于一个询问是否存在长度为 \(d\) 的路径：

• 如果 \(x\) 和 \(d\) 同奇偶，且 \(d \ge x\)，那么这个长度为 \(d\) 的路径一定存在，因为可以从 \(a\) 走 \(x\) 步到 \(b\)，然后走两步在 \(b\) 与 \(b\) 相邻的点两点之前左右横跳，直到走的步数为 \(d\)。

• 但是如果 \(x\) 与 \(d\) 不同奇偶，路径就一定不存在吗？

考虑下面的情况：

随便两个点，奇偶的路径都是合法的。

那么容易想到，我们可以维护从 \(a\) 到 \(b\) 的偶数步最短路径长度和奇数步最短路径长度。这一点显然可以用 Dijkstra 搞出来。

然后我们根据 \(d\) 的奇偶，判断对应的 \(a\) 到 \(b\) 的最短路径长度是否存在，存在的话并且长度小于等于 \(d\)，那么长度为 \(d\) 的路径就可以被构造出来。

于是这题就差不多结束了。

---

但是还有一组恶心的特判：

3 1 1
1 2
3 3 2

如果一个点是孤立的，那么怎么走都无解！

代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int N = 5005, K = 1e6 + 5;
struct Edge {int now, nxt;} e[N << 1];
int head[N], cur;
void add(int u, int v)
{
	e[++cur].now = v, e[cur].nxt = head[u];
	head[u] = cur;
}
int dis[N][2]; //分奇偶
bool inque[N];
void spfa(int s)
{
	memset(dis, 0x3f, sizeof dis);
	memset(inque, false, sizeof inque);
	queue <int> q;
	q.push(s), inque[s] = true, dis[s][0] = 0;
	while (!q.empty())
	{
		int u = q.front();
		q.pop(), inque[u] = false;
		for (int i = head[u]; i; i = e[i].nxt)
		{
			int v = e[i].now;
			if (dis[u][0] + 1 < dis[v][1])
			{
				dis[v][1] = dis[u][0] + 1;
				if (!inque[v]) inque[v] = true, q.push(v);
			}
			if (dis[u][1] + 1 < dis[v][0])
			{
				dis[v][0] = dis[u][1] + 1;
				if (!inque[v]) inque[v] = true, q.push(v);
			}
		}
	}
}
struct Query {int id, v, w;};
vector <Query> query[N];
bool ans[K];
int main()
{
	//ios::sync_with_stdio(false);
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	while (m--)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	for (int i = 1; i <= k; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		query[u].push_back((Query){i, v, w});
	}
	for (int u = 1; u <= n; u++)
		if (!query[u].empty() && head[u]) //特别注意！如果这个点是孤立的，怎么走都是无解
		{
			spfa(u);
			for (Query t : query[u]) ans[t.id] = (t.w >= dis[t.v][t.w & 1]);
		}
	for (int i = 1; i <= k; i++)
		if (ans[i]) puts("TAK"); else puts("NIE");
	return 0;
}

希望能帮助到大家！

标签：int,题解,路径,P3556,长度,include,inque,dis
From： https://www.cnblogs.com/liangbowen/p/16991082.html