题意简述

给一个 ( ) 个点 条边的可能有重边自环的无向图，进行 ( ) 次操作，操作分为三种：增加一条边，删去一条边，询问所有的 个点对的最短路和；要求对每个询问作出回答。

解题思路

• 如果只有增加边和查询的操作，那么可以参考 CF25C；使用Floyd算法在每次增加边的时候 更新最短路答案即可。

• 然后发现删除边的操作不好做，应该想办法绕过删除。

• 可以发现如果倒着看操作，那么删除操作可以变成增加边的操作。

• 我们先只关注初始的 条边，先执行所有的删边操作，可以通过Floyd 得到一个最短路的数组。

• 之后倒着操作，那么每次遇到初始前 条边的删除边操作，就是当作是加上一条边。

• 此时对于每次查询操作，可以把查询操作前面的增加边并且在查询时边未被删除的增加边操作给加上。

• 这样子做时间复杂度是 显然会超时，因此考虑对查询操作分块。

• 将操作分为 块，每块 个询问。

• 还是先关注初始 条边，先执行完所有删除操作后倒着操作，将删边变成加边。

• 在每个块下面，记录一个最短路数组。

• 之后正着进行操作，对于一个加边操作，如果这条边能完整存在一个块里，则将这条边加入这个块的最短路数组中，这里最多加入 个块中，时间复杂度 。

• 对于删除操作什么都不用做。

• 对于查询操作，先找到这个块中记录的最短路数组，然后在这个块中有查询操作之前的添加边操作，并且这个添加操作没有在查询时被删除，将这条边加入最短路数组；同理如果查询操作后面有删除边操作，并且这条边的添加在查询操作之前，则将删除的这条边加入最短路数组。在这里最多进行 次添加边操作，时间复杂度 。

• 因此分块后的时间复杂度为 ，可以通过本题。

参考代码

#include <bits/stdc++.h>

using i64 = long long;

using namespace std;

void solve() {
	int n,m,q,ym;
	cin>>n>>m>>q;
	ym=m;
	
	vector<int> l(m+q+10,0);
	vector<int> r(m+q+10,0);
	vector<int> v(m+q+10,0);
	
	for (int i=1; i<=m; i++)
	{
		cin>>l[i]>>r[i]>>v[i];
	}
	vector<int> op(q+10);
	vector<int> ll(q+10);
	vector<int> rr(q+10);
	vector<int> vv(q+10);
	vector<int> hao(q+10);
	vector<int> jin(m+q+10,0);
	
	for (int i=1; i<=q; i++)
	{
		cin>>op[i];
		if (op[i]==1)
		{
			cin>>ll[i]>>rr[i]>>vv[i];
			m++;
			hao[i]=m;
			l[m]=ll[i];
			r[m]=rr[i];		
			v[m]=vv[i];
		}
		if (op[i]==2)
		{
			cin>>ll[i];
			if (ll[i]<=ym)
			  jin[ll[i]]=1;
		}
	}

	
	int kuai=sqrt(q);
	vector dpp(n+5,vector<i64>(n+5,1e18));
	vector ji(kuai+5,dpp);
	
	auto dp=dpp;
	for (int i=1; i<=ym; i++)
	  if (!jin[i])
	  {
	  	dp[l[i]][r[i]]=min(dp[l[i]][r[i]],(i64)v[i]);
	  	dp[r[i]][l[i]]=min(dp[r[i]][l[i]],(i64)v[i]);
	  }
	for (int i=1; i<=n; i++)
	  dp[i][i]=0;
	
	for (int k=1; k<=n; k++)
	  for (int i=1; i<=n; i++)
	    for (int j=1; j<=n; j++)
	      dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
	
	int fn=0;
	int ccf=0;
	vector<int> nc(q+10,0);
	for (int i=q; i>=1; i--)
	{
		if (fn%kuai==0)
			ji[fn/kuai]=dp;
		
		if (op[i]==2)
		{
			if (ll[i]<=ym)
			{
				for (int pi=1; pi<=n; pi++)
				  for (int pj=1; pj<=n; pj++)
				  {
				    dp[pi][pj]=min(dp[pi][pj],dp[pi][l[ll[i]]]+v[ll[i]]+dp[r[ll[i]]][pj]);
					dp[pi][pj]=min(dp[pi][pj],dp[pi][r[ll[i]]]+v[ll[i]]+dp[l[ll[i]]][pj]);
				  }
			}
		}
		fn++;
	}
	
	for (int i=1; i<=q; i++)
	{
		if (op[i]==1)
		{
			int fl=0;
			for (int ii=i; ii<=q; ii++)
			{
				if (op[ii]==2 && ll[ii]==hao[i])
				  break;
				if ((q-ii)%kuai==0)
				{
					if (fl==0)
					  fl=1;
					else
					{
						int np=(q-ii)/kuai;
						for (int pi=1; pi<=n; pi++)
						  for (int pj=1; pj<=n; pj++)
						  {
						  	ji[np][pi][pj]=min(ji[np][pi][pj],ji[np][pi][ll[i]]+vv[i]+ji[np][rr[i]][pj]);
						    ji[np][pi][pj]=min(ji[np][pi][pj],ji[np][pi][rr[i]]+vv[i]+ji[np][ll[i]][pj]);
						  }
					}
				}
			}
		}
		
		if (op[i]==3)
		{
			int nk=(q-i)/kuai;
			int qi=max(q-(nk+1)*kuai+1,1);
			int zhong=q-nk*kuai;
			set<int> ran;
			for (int ii=qi; ii<i; ii++)
			{
				if (op[ii]==1)
				  ran.insert(hao[ii]);
				if (op[ii]==2)
				  ran.erase(ll[ii]);
			}
			for (int ii=zhong; ii>i; ii--)
			{
				if (op[ii]==2)
				  ran.insert(ll[ii]);
				if (op[ii]==1)
				  ran.erase(hao[ii]);
			}
			dp=ji[nk];
			for (auto gk:ran)
			{
				for (int pi=1; pi<=n; pi++)
				  for (int pj=1; pj<=n; pj++)
				  {
				  	dp[pi][pj]=min(dp[pi][pj],dp[pi][l[gk]]+v[gk]+dp[r[gk]][pj]);
				  	dp[pi][pj]=min(dp[pi][pj],dp[pi][r[gk]]+v[gk]+dp[l[gk]][pj]);
				  }
			}
			
						
			long long ans=0;
			for (int pi=1; pi<=n; pi++)
			  for (int pj=1; pj<=n; pj++)
			  {
			  	if (dp[pi][pj]<=1e17)
			       ans=ans+dp[pi][pj];
			  }
			cout<<ans%998244353<<'\n';
			
		}
	}
	
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t=1;
    std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}