luogu - 3556

发表于 | 分类于 | 浏览
字数统计: 694 | 阅读时长 ≈ 3

luogu - 3556 [POI2013]MOR-Tales of seafaring

题目大意

给定无向图$G=(V,E)$，$|V|=n$，$|E|=m$，有$k$个询问，问你$x$和$y$之间有没有长度为$d$的路径

数据范围

$2\leq n \leq 5000$

$1 \leq m \leq 5000$

$1 \leq d \leq 1e^9$

解题思路

既然是无向图，那么我们可以在某条边上来回走，那么我们只用处理处$x$到$y$的奇数最短路和偶数最短路即可，但是$k$的范围过大，如果对于每一次询问都进行一次$bfs$显然会超时，由于$n$只有$5000$，则说明$k$次询问中有很多重复的节点，我们考虑使用二维数组记录已经处理过的节点，避免重复运算

注意：

  1. 二维数组要是用$short$而不能使用$int$类型，否则会超出内存
  2. 要判断$x = y$的情况，有可能是孤立点，那么就不存在长度为$2$的路径
  3. 要判断$x$与$y$不连通的情况
  4. 本题卡常数，要开O2优化

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5001;
vector<int> v[maxn];
bool vis[maxn];
bool check[maxn];
short dis[maxn][maxn][2];
inline void bfs(register int s) {
    register queue<int> que;
    que.push(s);
    memset(vis, false, sizeof(vis));
    dis[s][s][0] = 0;
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        vis[u] = false;
        int len = v[u].size();
        for(int i = 0; i < len; ++i) {
            if(dis[s][v[u][i]][1] > dis[s][u][0] + 1) {
                dis[s][v[u][i]][1] = dis[s][u][0] + 1;
                if(!vis[v[u][i]]) {
                    que.push(v[u][i]);
                    vis[v[u][i]] = true;
                }
            }
            if(dis[s][v[u][i]][0] > dis[s][u][1] + 1) {
                dis[s][v[u][i]][0] = dis[s][u][1] + 1;
                if(!vis[v[u][i]]) {
                    que.push(v[u][i]);
                    vis[v[u][i]] = true;
                }
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    register int n, m, k;
    cin >> n >> m >> k;
    for(register int i = 1; i <= m; ++i) {
        register int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    fill(dis[0][0], dis[0][0] + maxn * maxn * 2, 32767);
    for(register int i = 1; i <= k; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        if(!check[x]) {
            bfs(x);
            check[x] = true;
        }
        if(x == y) {
            if(!z) cout << "TAK" << '\n';
            else if(z % 2 == 0) {
                if(v[x].size()) cout << "TAK" << '\n';
                else cout << "NIE" << '\n';
            }
            else {
                if(dis[x][y][1] != 32767 && z >= dis[x][y][1]) cout << "TAK" << '\n';
                else cout << "NIE" << '\n';
            }
            continue;
        }
        if(dis[x][y][0] != 32767 && z >= dis[x][y][0] && z % 2 == dis[x][y][0] % 2) cout << "TAK" << '\n';
        else if(dis[x][y][1] != 32767 && z >= dis[x][y][1] && z % 2 == dis[x][y][1] % 2) cout << "TAK" << '\n';
        else cout << "NIE" << '\n';
    }
    return 0;
}