Description
告别了随机的国度，这回小Q来到了一个陌生的国度。这个国度由n座城市和若干条单向道路构成，城市依次编号为
1到n。这个国度的路况变化非常频繁，而充满好奇的小Q想在这里进行许多次旅行，在每次出发之前，他会使用导
航系统计算两点间最少需要多少时间。请写一个程序，帮助小Q计算两点间的最短路，你需要支持以下两种操作： C x y z
从x点出发到y结束的单向道路通过时间变为了z(1<=z<=4)，z=0表示不可通行。 Q x
令d_i为x出发到i的最短路，若无解则为0，计算sum_{i=1}^n i*d_i。
Input
第一行包含两个正整数n,m(1<=n<=500,1<=m<=50000)，分别表示点数和操作次数。
接下来n行，每行n个整数w_{i,j}(0<=w_{i,j}<=4)，其中w_{i,j}表示i出发到j的单向道路的通过时间，0表示不可通行。
接下来m行，每行描述一个操作。 输入数据保证询问次数不超过5000次。
Output
对于每个询问输出一行一个整数，即sum_{i=1}^n i*d_i。
Sample Input
4 3
0 1 2 3
2 0 4 2
0 0 0 3
4 0 4 0
Q 1
C 1 3 0
Q 1
Sample Output
20
29
题解
其实官方题解还是不是很清楚的
这类最短路且边权很小的话，要不就把贡献拆到点上或者像这题这样维护
考虑一个连通块的BFS是怎么扩展的
显然就是先走1的边 走完1的再走2的 走完2的再走3的…以此类推
会发现每个点被第一次访问到的时候总是最小的路径长度
维护4个bitset表示距离当前已经访问过的点组成的连通块长度为1，2，3，4的点集是什么
每次取出距离为1的扩展，然后再把那些点加入这4个bitset
扫连通块的时候就动态移动一下这4个bitset，做到扫完长度为1的就去做长度为2的
发现每个点只会被访问一次，于是你还可以维护一个bitset表示哪些点还没有被访问过
复杂度就是 n ? n ? q 32 \frac{n*n*q}{32} 32n?n?q?的
如果直接拆点的话复杂度会暴涨成 n 4 q 32 \frac{n^4q}{32} 32n4q?的…变得很难受
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(LL x)
{
if(x<0){
putchar('-');x=-x;}if(!x){
putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
write(x);putchar(' ');}
inline void pr2(LL x){
write(x);putchar('\n');}
const int MAXN=505;
bitset<MAXN> nxt[5][MAXN];
bitset<MAXN> now,u1,g1[5];
int n,m,mp[MAXN][MAXN],d[MAXN],lin[MAXN];
bool v[MAXN];
char ch[10];
queue<int> li;
LL qry(int st)
{
now.set();now[st]=0;for(int i=1;i<=4;i++)g1[i]=nxt[i][st];memset(d,0,sizeof(d));int inf=d[0];d[st]=0;int c1=1,c2=0,o=0,dis=0;while(c1<n){
o=o%4+1;dis++;u1=now&g1[o];int tot=0;for(int i=u1._Find_first();i<u1.size();i=u1._Find_next(i)){
d[i]=dis;now[i]=0;tot++;g1[o%4+1]|=nxt[1][i];g1[(o+1)%4+1]|=nxt[2][i];g1[(o+2)%4+1]|=nxt[3][i];g1[(o+3)%4+1]|=nxt[4][i];}if(!tot)c2++;else c2=0;if(c2==5)break;c1+=tot;}LL ans=0;for(int i=1;i<=n;i++)ans+=(LL)i*d[i];return ans;
}
int main()
{
n=read();m=read();for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
int c=mp[i][j]=read();if(c)nxt[c][i][j]=1;}while(m--){
scanf("%s",ch+1);int u=read();if(ch[1]=='C'){
int v=read(),c=read();if(mp[u][v])nxt[mp[u][v]][u][v]=0;if(c)nxt[c][u][v]=1;mp[u][v]=c;}else pr2(qry(u));}return 0;
}