BZOJ 5097: [Lydsy1711月赛]实时导航（最短路 + bitset）

时间：2021-10-19 15:48:19

题意

\(n​\) 个点的有向图，边权 \(\in \{1, 2, 3, 4\}​\) ，\(m​\) 次修改边权/加边/删边，\(q​\) 次询问：以 \(s_i​\) 为起点，输出它到其他点的最短路。

\(n ≤ 5 \times 10^2 ,m \le 5 \times 10^4 , q \le 5 \times 10^3\)

题解

这图很密，如果修改就做一遍 \(Dijsktra\) 是 \(O((n + m) \log n)\) 的复杂度，显然是过不去的。

但是发现边权似乎不大，我们考虑把这些要进来的点压到 std :: bitset<N> 里面。

也就是我们维护到当前距离为 \(1, 2, 3, 4\) 的队列，然后我们把图也可以用 std :: bitset<N> 存下来。

然后每次就把要进来的点 或（or）上当前维护队列就行了，每次就循环移位就可以了。

然后每次取 std :: bitset<N> 的元素就行了，这里有两个骚操作 _Find_first() 以及 _Find_next(u) ，可以快速查找 std :: bitset<N> 的元素。

最后复杂度就是 \(\displaystyle O(\frac{qn^2}{\omega} + m)\) 的，看起来很科学qwq

总结

对于稠密图，可以考虑用 std :: bitset 来优化复杂度，加快暴力操作。

然后对于边权小，可以考虑用普通队列来替代优先队列，常常会得到更优秀的复杂度。

代码

具体看代码操作就行了。

/**************************************************************

    Problem: 5097

    User: zjp_shadow

    Language: C++

    Result: Accepted

    Time:10624 ms

    Memory:2440 kb

****************************************************************/

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Set(a, v) memset(a, v, sizeof(a))

#define Cpy(a, b) memcpy(a, b, sizeof(a))

#define debug(x) cout << #x << ": " << (x) << endl

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

template<typename T> inline bool chkmin(T &a, T b) {return b < a ? a = b, 1 : 0;}

template<typename T> inline bool chkmax(T &a, T b) {return b > a ? a = b, 1 : 0;}

inline int read() {

    int x(0), sgn(1); char ch(getchar());

    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;

    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);

    return x * sgn;

}

void File() {

#ifdef zjp_shadow

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

    freopen ("5097.out", "w", stdout);

#endif

}

const int N = 510;

int val[N][N];

typedef bitset<N> Info;

Info G[N][4]; int dis[N], que[N], len, n, m;

void Bfs(int S) {

    Info Q[4];

    For (i, 0, 3) Q[i] = G[S][i];

    Set(dis, 0); dis[S] = -1;

    for (int cur = 0, tim = 1, o = 0; cur < 5; ++ tim, o = (o + 1) % 4) {

        len = 0;

        for (int v = Q[o]._Find_first(); v < (int)Q[o].size(); v = Q[o]._Find_next(v)) {

            Q[o][v] = false; if (!dis[v]) que[++ len] = v;

        }

        For (i, 1, len) {

            int u = que[i]; dis[u] = tim;

            Q[(o + 1) % 4] |= G[u][0];

            Q[(o + 2) % 4] |= G[u][1];

            Q[(o + 3) % 4] |= G[u][2];

            Q[o] |= G[u][3];

        }

        cur = !len ? cur + 1 : 0;

    }

    int ans = 0;

    For (i, 1, n) if (i != S)

        ans += i * dis[i];

    printf ("%d\n", ans);

}

int main () {

    File();

    n = read(); m = read();

    For (i, 1, n) For (j, 1, n) {

        int w = read(); val[i][j] = w;

        if (w) G[i][w - 1][j] = true;

    }

    For (i, 1, m) {

        char opt[5];

        scanf ("%s", opt + 1);

        if (opt[1] == 'Q') Bfs(read());

        else {

            int u = read(), v = read(), w = read();

            if (val[u][v]) G[u][val[u][v] - 1][v] = false;

            val[u][v] = w;

            if (w) G[u][w - 1][v] = true;

        }

    }

    return 0;

}

相关文章