TIOJ 1749：[APIO '11] Path

TIOJ 1749：[APIO '11] Path

題目大意：平面上有兩個點 $(sx,sy),(ex,ey)$ 和 $n$ 個邊與座標軸平行的矩形，矩形皆不相交，只能在矩形上轉彎，問從 $(sx,sy)$ 走到 $(ex, ey)$ 的最短距離，或是不可能。

解法：我的第一種作法是把所有 $x,y$ 座標離散化，然後對這 $O(n^2)$ 個點建邊，結果 $\texttt{MLE}$ 了，然後我把距離的 $\texttt{long long}$ 改用一個 $\texttt{int}$ 跟 $\texttt{short}$ 存，空間壓過了，可是 $\texttt{TLE}$ 了。之後觀察到每次走的邊其中一個端點一定是起終點或矩形頂點，所以可以只對這些點建邊，寫了很久才過。

$\text{Code：}$

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const ll INF = 1e18;
const int SIZE = 1005;
const int mask = (1 << 10) - 1;

struct LIS {
    vector<int> lis;
    void init() {
        lis.clear();
    }
    void add(int x) {
        lis.pb(x);
    }
    void work() {
        sort(lis.begin(), lis.end());
        lis.erase(unique(lis.begin(), lis.end()), lis.end());
    }
    int id(int x) {
        return lower_bound(lis.begin(), lis.end(), x) - lis.begin() + 1;
    }
    int operator [] (const int& x) const {
        return lis[x - 1];
    }
} lisx, lisy;

int n, szx, szy;
int sx, sy, ex, ey;
pair<int, int> x[SIZE], y[SIZE];
vector<pair<int, short>> vx[2 * SIZE], vy[2 * SIZE];

int sz;
unordered_set<int> us;
unordered_map<int, int> mp;
vector<vector<pair<int, int>>> adj;
vector<ll> dis;
inline int id(int x, int y) {
    return (x - 1) * szy + y - 1;
}
inline int mid(int x, int y) {
    if (!mp.count(id(x, y))) mp[id(x, y)] = sz++;
    return mp[id(x, y)];
}

void solve() {
    cin >> sx >> sy >> ex >> ey;
    cin >> n;
    FOR (i, 1, n) {
        cin >> x[i].F >> y[i].F >> x[i].S >> y[i].S;
        if (x[i].F > x[i].S) swap(x[i].F, x[i].S);
        if (y[i].F > y[i].S) swap(y[i].F, y[i].S);
    }

    lisx.init(), lisx.add(sx), lisx.add(ex);
    lisy.init(), lisy.add(sy), lisy.add(ey);
    FOR (i, 1, n) {
        lisx.add(x[i].F), lisx.add(x[i].S);
        lisy.add(y[i].F), lisy.add(y[i].S);
    }
    lisx.work(), sx = lisx.id(sx), ex = lisx.id(ex);
    lisy.work(), sy = lisy.id(sy), ey = lisy.id(ey);
    FOR (i, 1, n) {
        x[i].F = lisx.id(x[i].F), x[i].S = lisx.id(x[i].S);
        y[i].F = lisy.id(y[i].F), y[i].S = lisy.id(y[i].S);
    }

    szx = lisx.lis.size(), szy = lisy.lis.size();
    FOR (x, 1, szx) vx[x].clear();
    FOR (y, 1, szy) vy[y].clear();
    int stx = 1, sty = 1, etx = 1, ety = 1, sid = 0, eid = n + 1;
    auto add = [&](int i, int x, int y, int tx, int ty, int is = 0) {
        if (!is && x == sx && y == sy) {
            sid = i;
            stx |= tx, sty |= ty;
            return;
        }
        if (!is && x == ex && y == ey) {
            eid = i;
            etx |= tx, ety |= ty;
            return;
        }
        vx[x].pb(y, tx << 10 | i);
        vy[y].pb(x, ty << 10 | i);
    };
    FOR (i, 1, n) {
        for (int cx : {x[i].F, x[i].S}) for (int cy : {y[i].F, y[i].S}) add(i, cx, cy, 1, 1);
        FOR (j, x[i].F + 1, x[i].S - 1) {
            add(i, j, y[i].F, 2, 0);
            add(i, j, y[i].S, 0, 0);
        }
        FOR (j, y[i].F + 1, y[i].S - 1) {
            add(i, x[i].F, j, 0, 2);
            add(i, x[i].S, j, 0, 0);
        }
    }
    add(sid, sx, sy, stx, sty, 1);
    add(eid, ex, ey, etx, ety, 1);

    sz = 0, us.clear(), mp.clear(), adj.clear(), dis.clear();
    FOR (x, 1, szx) {
        sort(vx[x].begin(), vx[x].end());
        for (int i = 0; i < vx[x].size(); i++) if (vx[x][i].S >> 10 & 1) {
            us.insert(id(x, vx[x][i].F));
            if (i > 0 && ((vx[x][i - 1].S >> 10 & 1) || (vx[x][i - 1].S & mask) != (vx[x][i].S & mask))) us.insert(id(x, vx[x][i - 1].F));
            if (i + 1 < vx[x].size() && !(vx[x][i].S >> 10 & 2) && ((vx[x][i + 1].S >> 10 & 1) || (vx[x][i + 1].S & mask) != (vx[x][i].S & mask))) us.insert(id(x, vx[x][i + 1].F));
        }
    }
    FOR (y, 1, szy) {
        sort(vy[y].begin(), vy[y].end());
        for (int i = 0; i < vy[y].size(); i++) if (vy[y][i].S >> 10 & 1) {
            us.insert(id(vy[y][i].F, y));
            if (i > 0 && ((vy[y][i - 1].S >> 10 & 1) || (vy[y][i - 1].S & mask) != (vy[y][i].S & mask))) us.insert(id(vy[y][i - 1].F, y));
            if (i + 1 < vy[y].size() && !(vy[y][i].S >> 10 & 2) && ((vy[y][i + 1].S >> 10 & 1) || (vy[y][i + 1].S & mask) != (vy[y][i].S & mask))) us.insert(id(vy[y][i + 1].F, y));
        }
    }
    adj.resize(us.size()), dis.resize(us.size(), INF);
    FOR (x, 1, szx) {
        int ly = -1, lt;
        for (int i = 0; i < vx[x].size(); i++) if (us.count(id(x, vx[x][i].F))) {
            auto [y, t] = vx[x][i];
            if (ly != -1 && !(lt & 2)) {
                adj[mid(x, ly)].pb(mid(x, y), lisy[y] - lisy[ly]);
                adj[mid(x, y)].pb(mid(x, ly), lisy[y] - lisy[ly]);
            }
            ly = y, lt = t >> 10;
        }
    }
    FOR (y, 1, szy) {
        int lx = -1, lt;
        for (int i = 0; i < vy[y].size(); i++) if (us.count(id(vy[y][i].F, y))) {
            auto [x, t] = vy[y][i];
            if (lx != -1 && !(lt & 2)) {
                adj[mid(lx, y)].pb(mid(x, y), lisx[x] - lisx[lx]);
                adj[mid(x, y)].pb(mid(lx, y), lisx[x] - lisx[lx]);
            }
            lx = x, lt = t >> 10;
        }
    }

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    pq.emplace(dis[mid(sx, sy)] = 0, mid(sx, sy));
    while (pq.size()) {
        auto [d, pos] = pq.top();
        pq.pop();
        if (d > dis[pos]) continue;
        if (pos == mid(ex, ey)) {
            cout << d << '\n';
            return;
        }
        for (auto [np, w] : adj[pos]) if (d + w < dis[np]) pq.emplace(dis[np] = d + w, np);
    }
    cout << "No Path\n";
}

int main() {
    Waimai;
    int tt;
    cin >> tt;
    while (tt--) solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！