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 = ;

const ll inf = 0x3f3f3f3f3f3f3f3f;

int n, m, b[N][N], ufs[N][N], sx[], sy[];

ll a[N][N], dis[N][N], ans[];

bool vis[N][N];

struct Node {

    int x, y;

    ll d;

    inline Node (int nowX = , int nowY = , 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 = ; char ch = ; T op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    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 >  ? 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 = ; i <= n; i++)

        for(int j = ; j <= m + ; j++) {

            dis[i][j] = inf;

            ufs[i][j] = j;

            vis[i][j] = ;

        }

    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] + ;

    for(; !Q.empty(); ) {

        Node out = Q.top(); Q.pop();

        int x = out.x, y = out.y;

        if(vis[x][y]) continue;

        vis[x][y] = ;

        int ln = max(, 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(, 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 + ;

            }

        }

    }

}

int main() {

    freopen("4.in", "r", stdin);

//    freopen("my.out", "w", stdout);

    read(n), read(m);

    for(int i = ; i <= n; i++)

        for(int j = ; j <= m; j++)

            read(b[i][j]);

    for(int i = ; i <= n; i++)

        for(int j = ; j <= m; j++)

            read(a[i][j]);

    for(int i = ; i <= ; i++)

        read(sx[i]), read(sy[i]);

    for(int i = ; i <= ; i++) {

        dij(i);

        for(int j = ; j <= ; j++) ans[j] += dis[sx[j]][sy[j]];

    }

    ll res = inf, pos = ;

    for(int i = ; i <= ; i++)

        if(ans[i] < res) res = ans[i], pos = i;

    if(res >= inf) {

        puts("NO");

        return ;

    }

    if(pos == ) puts("X");

    if(pos == ) puts("Y");

    if(pos == ) puts("Z");

    printf("%lld\n", res);

    return ;

}

巴特西

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

最新文章

热门文章