Luogu 4473 [国家集训队]飞飞侠

BZOJ 2143

新技能：并查集优化最短路。

暴力最短路是$O(n^4)$的，然后拿个线段树优化一下连边就$O($能过$)$了。

但是这样都太慢了。

我们考虑一个点如果之前被更新过了，那么之后就不会被更新了，所以我们只要能跳过这个已经被更新过的点，直接去更新没有更新过的点就行了，刚好对应了一个并查集的路径压缩，这样子每一次跳到一个没有更新过的点就是$O(1)$的了。

每一个点拿出来的更新的时候其实是要付出它的点权，所以我们要把$dis_{x, y}  + a_{x, y}$一起丢到堆里去才能保证转移的正确性。

还是不会算时间复杂度，但是非常优秀。

Code：

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;

const int N = 155;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n, m, b[N][N], ufs[N][N], sx[4], sy[4];
ll a[N][N], dis[N][N], ans[4];
bool vis[N][N];

struct Node {
    int x, y;
    ll d;
    
    inline Node (int nowX = 0, int nowY = 0, ll nowD = 0LL) {
        x = nowX, y = nowY, d = nowD;
    }
    
    friend bool operator < (const Node &u, const Node &v) {
        return u.d > v.d;
    }
    
};
priority_queue <Node> Q;

template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

inline int max(int x, int y) {
    return x > y ? x : y;
}

inline int min(int x, int y) {
    return x > y ? y : x;
}

inline int abs(int x) {
    return x > 0 ? x : -x;
}

int find(int x, int y) {
    return ufs[x][y] == y ? y : ufs[x][y] = find(x, ufs[x][y]);
}

void dij(int st) {
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m + 1; j++) {
            dis[i][j] = inf;
            ufs[i][j] = j;
            vis[i][j] = 0;
        }
    dis[sx[st]][sy[st]] = 0LL;
    Q.push(Node(sx[st], sy[st], a[sx[st]][sy[st]]));
    ufs[sx[st]][sy[st]] = sy[st] + 1;
    for(; !Q.empty(); ) {
        Node out = Q.top(); Q.pop();
        int x = out.x, y = out.y;
        if(vis[x][y]) continue;
        vis[x][y] = 1;
        
        int ln = max(1, x - b[x][y]), rn = min(n, x + b[x][y]);
        for(int i = ln; i <= rn; i++) {
            int stp = b[x][y] - abs(i - x);
            int lm = max(1, y - stp), rm = min(m, y + stp);
            for(int j = find(i, lm); j <= rm; j = find(i, j)) {
                if(dis[i][j] > dis[x][y] + a[x][y]) {
                    dis[i][j] = dis[x][y] + a[x][y];
                    Q.push(Node(i, j, dis[i][j] + a[i][j]));
                }
                ufs[i][j] = j + 1;
            }
        }
    }
}

int main() {
    freopen("4.in", "r", stdin);
//    freopen("my.out", "w", stdout);
    
    read(n), read(m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            read(b[i][j]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            read(a[i][j]);
    
    for(int i = 1; i <= 3; i++)
        read(sx[i]), read(sy[i]);
    
    for(int i = 1; i <= 3; i++) {
        dij(i);
        for(int j = 1; j <= 3; j++) ans[j] += dis[sx[j]][sy[j]];
    }
    
    ll res = inf, pos = 0;
    for(int i = 1; i <= 3; i++)
        if(ans[i] < res) res = ans[i], pos = i;
        
    if(res >= inf) {
        puts("NO");
        return 0;
    }
    
    if(pos == 1) puts("X");
    if(pos == 2) puts("Y");
    if(pos == 3) puts("Z");
    
    printf("%lld
", res);
    return 0;
}