题解：P3556 [POI 2013] MOR-Tales of seafaring

· · 题解

由于路径不必是简单路，若存在一条从 s 到 t 的长度为 d 路径（通道），则必然存在从 s 到 t 的路径（通道）长度为 d,d+2,d+4,\cdots。

故只需对于每对点 (s,t) 求出从 s 到 t 的长度为奇数/偶数的最短路。

注意到 n,m 数据范围较小，从每个点出发进行一次 BFS，预处理所有最短路长度即可。

抽象代码

#include <bits/stdc++.h>
#define endl '\n'
#define panda(i, l, r) for (int i = l; i <= r; ++i)
#define adnap(i, l, r) for (int i = l; i >= r; --i)
using namespace std;
const int PDDD = 5000 + 63;
int n, m, k;
vector<int> G[PDDD];
short diaoda[PDDD][PDDD][2]; //坑点：本题用int空间会爆，用short节省空间 
void pddd(int u) { //BFS
    queue<pair<int, int>> qddd;
    memset(diaoda[u], -1, sizeof diaoda[u]);
    if (G[u].empty()) //特判u为孤立点 
        return;
    diaoda[u][u][0] = 0;
    qddd.push({ u, 0 });
    while (!qddd.empty()) {
        auto [pd, x] = qddd.front();
        qddd.pop();
        for (int qd : G[pd])
            if (diaoda[u][qd][x ^ 1] == -1)
                diaoda[u][qd][x ^ 1] = diaoda[u][pd][x] + 1, qddd.push({ qd, x ^ 1 });
    }
}
int main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> m >> k;
    panda(p, 1, m) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    panda(p, 1, n) pddd(p);
    while (k--) {
        int s, t, d;
        cin >> s >> t >> d;
        if (diaoda[s][t][d & 1] >= 0 && diaoda[s][t][d & 1] <= d)
            cout << "TAK" << endl;
        else
            cout << "NIE" << endl;
    }
}