【Luogu】每日一题——Day21. P3556 [POI 2013] MOR-Tales of seafaring (图论)

P3556 [POI 2013] MOR-Tales of seafaring - 洛谷

题目：

思路：

有点分层图的感觉

由于题目不是要求简单路径，因此我们可以反复走来刷路径，那么一个思路就是求最短路

如果对于询问 s->t 是否存在 d，那么就有两种情况，一个是 d < dis，即小于最短路，那么此时肯定无解，否则一定有解，具体的，如果 d 是奇数，那么我们可以考虑一个走了奇数步的最短路，然后反复刷步数得到，而偶数也是一样的考虑偶数

所以维护奇数偶数的最短路即可，spfa秒了

代码：

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;#define yes cout << "YES" << endl
#define no cout << "NO" << endl
vector<vector<short>> g(5005);
int dis[5005][2];
bool inq[5005];
int n, m, k;
bool ans[1000005];
bool hasfa[5005];struct MyStruct
{int b, d, id;
};
vector<vector<MyStruct>> ask(5005);void spfa(int fa)
{memset(dis, 0x3f, sizeof dis);memset(inq, 0, sizeof inq);queue<int> q;dis[fa][0] = 0;inq[fa] = 1;q.push(fa);while (!q.empty()){auto t = q.front();q.pop();inq[t] = 0;for (auto & son : g[t]){if (dis[son][1] > dis[t][0] + 1){dis[son][1] = dis[t][0] + 1;if (!inq[son]){inq[son] = 1;q.push(son);}}if (dis[son][0] > dis[t][1] + 1){dis[son][0] = dis[t][1] + 1;if (!inq[son]){inq[son] = 1;q.push(son);}}}}
}void solve()
{cin >> n >> m >> k;for (int i = 0; i < m; i++){int u, v;cin >> u >> v;g[u].emplace_back(v);g[v].emplace_back(u);hasfa[u] = hasfa[v] = 1;}for (int i = 0; i < k; i++){int a, b, d;cin >> a >> b >> d;ask[a].push_back({ b, d, i });}for (int i = 1; i <= n; i++){if (!hasfa[i] || ask[i].empty()){continue;}spfa(i);for (auto & query : ask[i]){ans[query.id] = (query.d >= dis[query.b][query.d & 1]);}}for (int i = 0; i < k; i++){cout << (ans[i] ? "TAK" : "NIE") << endl;}
}
signed main()
{cin.tie(0)->sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int t = 1;//cin >> t;while (t--){solve();}return 0;
}