题解：CF2279D Meta Graph

· · 题解

较为简单易懂的做法

题意

给你一个无向简单连通图，问从当前状态 (a, b) 走到状态 (c, d) 的最短路。

有两种状态转移两种均是在存在边 (u, v) 的情况下成立：

  1. (u, v) \Leftrightarrow (v, u)
  2. (x, u) \Leftrightarrow (x, v)

范围：n, m \le 2 \times 10^5。

题解

显然，如果 a = c，b 走到 d 即可。如果 a \neq c，b 就要走到 a 的相邻节点，且这个相邻节点到 c 的距离比 a 到 c 的距离近，然后用一次操作一，此时 a 距离 c 更近了，反复操作，每次都是从 a 的一个相邻节点走到另一个相邻节点，直到 a = c，然后 b 再走到 d。

考虑这一过程用到了那些点/边，首先 (u, v) \Leftrightarrow (v, u) 用到了，(a, u) \Leftrightarrow (a, v) 和 (c, u) \Leftrightarrow (c, v) 用到了，还有就是 (u, u) \Leftrightarrow (u, v)。把这些点离散化，把边连起来，跑一遍 bfs 即可。（常数有点大，请勿使用 map）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
    ll n, m, stx, sty, edx, edy;
    cin >> n >> m >> stx >> sty >> edx >> edy;
    vector<pair<ll, ll>> e;
    vector<ll> xs;
    xs.push_back(1ll * stx * n + sty);
    xs.push_back(1ll * edx * n + edy);
    for (int i = 1; i <= m; i++) {
        ll u, v;
        cin >> u >> v;
        e.push_back({1ll * u * n + v, 1ll * v * n + u});
        e.push_back({1ll * v * n + u, 1ll * u * n + v});
        e.push_back({1ll * u * n + u, 1ll * u * n + v});
        e.push_back({1ll * u * n + v, 1ll * u * n + u});
        e.push_back({1ll * v * n + u, 1ll * v * n + v});
        e.push_back({1ll * v * n + v, 1ll * v * n + u});
        e.push_back({1ll * stx * n + u, 1ll * stx * n + v});
        e.push_back({1ll * stx * n + v, 1ll * stx * n + u});
        e.push_back({1ll * edx * n + u, 1ll * edx * n + v});
        e.push_back({1ll * edx * n + v, 1ll * edx * n + u});
    }
    for (auto &p : e) {
        xs.push_back(p.first);
        xs.push_back(p.second);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    auto id = [&](ll x) {
        return int(lower_bound(xs.begin(), xs.end(), x) - xs.begin());
    };
    vector<vector<int>> g(xs.size());
    for (auto &p : e) {
        g[id(p.first)].push_back(id(p.second));
    }
    auto get_dis = [&](int st, vector<int> &dis) {
        dis[st] = 0;
        deque<int> q;
        q.push_front(st);
        while(q.size()){
            int u = q.front();
            q.pop_front();
            for (auto v : g[u]) {
                if (v == st || dis[v]) continue;
                q.push_back(v);
                dis[v] = dis[u] + 1;
            }
        }
    };
    vector<int> dis(xs.size(), 0);
    get_dis(id(1ll * stx * n + sty), dis);
    cout << dis[id(1ll * edx * n + edy)] << '\n';
}
signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}