BZOJ

分析

暴力做法是每次修改后跑一遍 dijkstra,显然是过不去的。

注意到 $1\leq w\leq 4$,因此我们可以开 $4$ 个队列,分别维护到当前点距离为 $1,2,3,4$ 的点。但是这样子还是过不去。

然后有一个很 $\mathsf{\color{black}{x}\color{red}{gzc}}$ 的做法。我们用 bitset 代替队列,即开 $4$ 个 bitset,第 $i$ 个 bitset 中到当前点距离为 $i$ 的点为 $1$,其它点为 $0$;然后我们再开 $4$ 个 bitset 分别维护边权为 $1,2,3,4$ 的边。

这样子每次扩展就很容易了,按位或一下然后再循环移位即可。

时间复杂度 $\mathcal{O}(\frac{qn^2}{\omega}+m)$ 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500+10,M=50000+10;

int n,m;
int w[N][N]; bitset<N> G[5][N];
bitset<N> Q[5]; queue<int> q;
int dis[N],vis[N];

inline int bfs(int s) {
    memset(vis,0,sizeof(vis)),memset(dis,0,sizeof(dis));
    vis[s]=1; for (re int i=1;i<=4;++i) Q[i]=G[i][s];
    for (re int h=1,d=1,p=1;h<=4;++d,p=p%4+1) { int flag=0;
        for (re int v=Q[p]._Find_first();v<=n;v=Q[p]._Find_next(v)) {
            Q[p][v]=0;
            if (!vis[v]) dis[v]=d,vis[v]=1,q.push(v),flag=1;
        }
        while (!q.empty()) {
            int u=q.front(); q.pop();
            for (re int i=1;i<=4;++i)
                Q[(p+i)%4+((p+i)%4?0:4)]|=G[i][u];
        }
        h=flag?1:h+1;
    }
    int ans=0;
    for (re int i=1;i<=n;++i) ans+=i*dis[i];
    return ans;
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j) {
            w[i][j]=read();
            if (w[i][j]) G[w[i][j]][i][j]=w[i][j];
        }
    for (re int i=1;i<=m;++i) {
        char op[2]; scanf("%s",op);
        if (op[0]=='C') {
            int u=read(),v=read(),d=read();
            if (w[u][v]) G[w[u][v]][u][v]=0;
            if (w[u][v]=d) G[w[u][v]][u][v]=1;
        }
        else printf("%d\n",bfs(read()));
    }
    return 0;
}
最后修改:2019 年 10 月 30 日 10 : 28 AM