abc375_F
F - Road Blocked
思路
\(n\)的范围很小，考虑用\(floyd\)算法，对查询进行倒序的离线处理，原题目的删边就变为了增加边，每次增加边更新仅为\(O(n^2)\)
代码
struct Edge{
int a,b,c;
};
//离线处理，倒序进行，操作1就变为了加边操作，更新以该边两个点为中继点的g数组即可
void solve() {
int n,m,q;
cin>>n>>m>>q;
vector<Edge> es(m+1);
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
es[i]={a,b,c};
}
vector<tuple<int,int,int>> qs(q);
vector<bool> st(m+1);
for(auto &[op,x,y]: qs){
cin>>op;
if(op==1) cin>>x,y=0,st[x]=true;
else cin>>x>>y;
}
vector<vector<ll>> g(n+1,vector<ll>(n+1,1e18));
for(int i=1;i<=m;i++){
auto [a,b,c]=es[i];
if(!st[i]) g[a][b]=g[b][a]=c;
}
for(int i=1;i<=n;i++){
g[i][i]=0;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
}
}
vector<ll> ans;
for(int k=(int)qs.size()-1;k>=0;k--){
auto [op,x,y]=qs[k];
if(op==2){
ll res=g[x][y];
ans.push_back((res==1e18?-1:res));
}
else{
auto [a,b,c]=es[x];
g[a][b]=g[b][a]=min(g[a][b],(ll)c); //这里要取min，我当时直接赋值wa了好几发
//下面两个循环要分开写
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=min(g[i][j],g[i][a]+g[a][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=min(g[i][j],g[i][b]+g[b][j]);
}
}
}
}
reverse(ans.begin(),ans.end());
for(auto tt:ans) cout<<tt<<endl;
}
下面这种更新方法更为便捷，不用给g[a][b]再赋值，且可以写在一个循环里
G[u][v]=min(G[u][v],G[u][a[x[i]]]+c[x[i]]+G[b[x[i]]][v]);
G[u][v]=min(G[u][v],G[u][b[x[i]]]+c[x[i]]+G[a[x[i]]][v]);