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