题解

这题考虑到询问很小
于是我们可以考虑每一次询问都暴力做一次
那么问题就出在怎么做
又考虑到边权很小
于是我们可以进行一个特殊的BFS
首先，从一个x出发，肯定是先扩展与他距离为1的，距离为2的。。。如此类推
于是我们就可以这么想，我们每一次就优先扩展与当前联通块距离为1的，然后扩展为2的，为3的。。一直到扩展完
然后这个过程可以用四个bitset来维护
分别是距离当前为1的点集，2的点集，3的点集，4的点集
然后每一次就把1的拿出来，进行扩展。。
然后把2的变成1的，3的变成2的，4的变成3的
然后再与新扩展的点集弄起来。。
就可以了时间复杂度$O(n*n*q/32)$

CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<bitset>
using namespace std;
const int N=515;
int n,m;
bitset<N> s[N][10];//和他距离为这么多的 
int a[N][N];//地图
int f[N];
int d[N],tot;
void solve (int x)
{bitset<N> q[4];//当前每一个距离的栈for (int u=0;u<4;u++)   q[u]=s[x][u];memset(f,0,sizeof(f));f[x]=-1;int now=1;//现在更新了多少个点int o=0;int time=0;int cnt=0;while (now!=n)//没有更新完{time++;//当前的时间是多少 tot=0;for (int u=q[o]._Find_first();u<q[o].size();u=q[o]._Find_next(u)){q[o][u]=0;if (f[u]==0) d[++tot]=u;}for (int u=1;u<=tot;u++){int lalal=d[u];f[lalal]=time;q[(o+1)%4]|=s[lalal][0];q[(o+2)%4]|=s[lalal][1];q[(o+3)%4]|=s[lalal][2];q[(o+4)%4]|=s[lalal][3];}if (tot==0) cnt++;else cnt=0;if (cnt>=5) break;now=now+tot;o++;//平移if (o>=4) o=0;}int ans=0;for (int u=1;u<=n;u++){if (u==x) continue;ans=ans+f[u]*u;}printf("%d\n",ans);return ;
}
int main()
{memset(s,0,sizeof(s));scanf("%d%d",&n,&m);for (int u=1;u<=n;u++)for (int i=1;i<=n;i++){int x;scanf("%d",&x);a[u][i]=x;if (x!=0) s[u][x-1][i]=1;}for (int u=1;u<=m;u++){char ss[5];scanf("%s",ss);if (ss[0]=='Q')//询问{int x;scanf("%d",&x);solve(x);}else{int x,y,z;scanf("%d%d%d",&x,&y,&z);if (a[x][y]!=0) s[x][a[x][y]-1][y]=0;if (z!=0) s[x][z-1][y]=1;a[x][y]=z;}}return 0;
}