题解：SP10547 DELIVER - Delivery Route

· · 题解

思路

这道题如果忽略顺序，就只是一道黄，但是这题要求必须按照 1 \to 2,2\to3,3\to4,\cdots,n - 1\to n,n \to 1。那该如何操作呢？

此题可以和P3632 [APIO2011] 寻路一样运用类似的思 路，建图跑最短路。

先观察样例：

由于在 i \to j 的过程中不能经过其他任何点，也就是说，最多只能在其他点的周围运动，所以可以想到，在每个点的上下左右四个方向各建一个虚点，如果虚点和原来的点重合就不建。

也就是这样的：

再对虚点之间两两连边，但是要注意，如果连边必须是只有一个改变方向或没有改变方向，否则路径一定可以拆成数段路径拼接在一起。

建完图后就是这样的：

再从每个虚点为起点跑最短路，或者直接跑一个 floyd，再枚举起点和终点相邻的虚点，再求出虚点之间的最短路径 +2，就是两点之间的最短路径了。当然，还要特判一下，如果两个点相邻就不用枚举，最短路就是 1。

时间复杂度为：O(m \log n + n^2 \log m + n + n \log m + nm \log n)。

code：

#include<bits/stdc++.h>
using namespace std;

#define int long long
constexpr int fx[4] = {1, 0, -1, 0};
constexpr int fy[4] = {0, -1, 0, 1};

int n;
int x[109], y[109];
int cnt;
vector<int> g[509];
int a[509], b[509];
int d[509][509];
vector<pair<int, int> > e[509];
bitset<509> c[509];
map<pair<int, int>, int> p, q;
vector<int> l[2000009];
vector<int> r[2000009];

inline void input() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        p[{x[i], y[i]}] = i;
        l[x[i]].push_back(y[i]);
        r[y[i]].push_back(x[i]);
    }
}

inline void addd() {
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < 4; j++) {
            int cx = x[i] + fx[j];
            int cy = y[i] + fy[j];
            if(!p.count({cx, cy})) {
                if(!q.count({cx, cy})) {
                    q[{cx, cy}] = ++cnt;
                    a[cnt] = cx, b[cnt] = cy;
                    g[i].push_back(cnt);
                } else {
                    g[i].push_back(q[{cx, cy}]);
                }
            }
        }
    }
}

inline bool check(int _a, int _b, int _c, int _d) {
    if(p.count({_a, _b}) || p.count({_c, _d})) return 0;
    if(_a == _c) {
        if(!l[_a].size()) return 1;
        return upper_bound(l[_a].begin(), l[_a].end(), _b) == upper_bound(l[_a].begin(), l[_a].end(), _d);
    } else {
        if(!r[_b].size()) return 1;
        return upper_bound(r[_b].begin(), r[_b].end(), _a) == upper_bound(r[_b].begin(), r[_b].end(), _c);
    }
}

inline void add(int _a, int _b, int _u, int _c, int _d, int _v) {
    int cnt = abs(_b - _d) + abs(_a - _c);
    if(_a == _c || _b == _d) {
        if(check(_a, _b, _c, _d))e[_u].push_back({_v, cnt}), e[_v].push_back({_u, cnt});
        return;
    }
    if((check(_a, _b, _a, _d) && check(_a, _d, _c, _d)) || (check(_a, _b, _c, _b) && check(_c, _b, _c, _d))) e[_u].push_back({_v, cnt}), e[_v].push_back({_u, cnt});
}

inline void addedge() {
    for(int i = 1; i <= cnt; i++) {
        for(int j = i + 1; j <= cnt; j++) {
            add(a[i], b[i], i, a[j], b[j], j);
        }
    }
}

inline void dij(int s) {
    d[s][s] = 0;
    priority_queue<pair<int, int> > q;
    q.push({0, s});
    while(q.size()) {
        int u = q.top().second;
        q.pop();
        if(c[u][s]) continue;
        c[u][s] = 1;
        for(auto to: e[u]) {
            if(d[to.first][s] > d[u][s] + to.second) {
                d[to.first][s] = d[u][s] + to.second;
                q.push({-d[to.first][s], to.first});
            }
        }
    }
}

inline void zdl() {
    memset(d, 0x3f, sizeof(d));
    for(int i = 1; i <= cnt; i++) {
        dij(i);
    }
}

inline int num(int a, int b) {
    for(int i = 0; i < 4; i++) {
        int cx = x[a] + fx[i];
        int cy = y[a] + fy[i];
        if(cx == x[b] && cy == y[b]) return 1;
    }
    return 0;
}

inline int sum(int x, int y) {
    int z = num(x, y);
    if(z) return z;
    int minn = 0x3f3f3f3f3f3f3f3f;
    for(auto u: g[x]) {
        for(auto v:g[y]) {
            minn = min(minn, 2 + d[u][v]);
        }
    }
    if(minn == 0x3f3f3f3f3f3f3f3f) {
        cout << -1 << "\n";
        exit(0);
    }
    return minn;
} 

inline int ask() {
    int ans = sum(1, n);
    for(int i = 1; i < n; i++) {
        ans += sum(i, i + 1);
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    input();
    addd();
    for(int i = 0; i <= 1e6 + 1; i++) {
        if(l[i].size()) l[i].push_back(-1), l[i].push_back(1e6 + 9), sort(l[i].begin(), l[i].end());
        if(r[i].size()) r[i].push_back(-1), r[i].push_back(1e6 + 9), sort(r[i].begin(), r[i].end());
    }
    addedge();
    zdl();
    cout << ask();
    return 0;
}