AtCoder Beginner Contest 375 F - Road Blocked

题目大意

给你一个n个点m条边的无向图，接下来有两种操作
1.删除编号为 $i$ 的边
2.询问 $x,y$ 两点之间的最短路

思路

注意到 $n<=300$ ，而且我我们需要任意两点最短路，因此可以考虑使用 $Floyed$ 算法计算全源最短路
但是删除边这个操作属实是有点难受了，那我们怎么办呢？
我们可以考虑反向操作输入数据，不就变成了加边操作了嘛，这个就好处理了
对于每次加入的边，我们可以这样处理（可以理解为用这两个点将附近的点全部更新一次）
$dis[j][k]=min(dis[j][k],dis[j][u]+val+dis[v][k]);$
$dis[j][k]=min(dis[j][k],dis[j][v]+val+dis[u][k]);$
其中 $u,v$ 是加入的边的两个端点
后续的操作就没什么难度了
时间复杂度 $O(n^3+n^{2}q)$

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define rep(i,x,y) for(ll i=x;i<=y;++i)
#define per(i,x,y) for(ll i=x;i>=y;--i)
using namespace std;
typedef long long ll;
const ll V=2e5+100;
ll n,m,q;
ll a[V],g[500][500],b[V],c[V];
ll opt[V],x[V],y[V],cnt,ans[V];
ll dis[500][500];
bool pd[V];
inline ll in()
{ll res=0,f=1;char ch;while((ch=getchar())<'0'||ch>'9')if(ch=='-') f=-1;res=res*10+ch-'0';while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-'0';return res*f;
}
inline void put(ll x)
{if(x<0) putchar('-'),x*=-1;if(x>9) put(x/10);putchar(x%10+48);
}
int main()
{n=in(),m=in(),q=in();rep(i,1,n)rep(j,1,n)dis[i][j]=1e18;rep(i,1,n) dis[i][i]=0;rep(i,1,m) a[i]=in(),b[i]=in(),c[i]=in();rep(i,1,q){opt[i]=in(),x[i]=in();if(opt[i]==2) y[i]=in();else pd[x[i]]=true ;}rep(i,1,m)if(!pd[i])dis[a[i]][b[i]]=dis[b[i]][a[i]]=c[i];rep(k,1,n)rep(i,1,n)rep(j,1,n)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);per(i,q,1){if(opt[i]==1){ll u=a[x[i]],v=b[x[i]],val=c[x[i]];
//			dis[u][v]=dis[v][u]=val;rep(j,1,n)rep(k,1,n){dis[j][k]=min(dis[j][k],dis[j][u]+val+dis[v][k]);dis[j][k]=min(dis[j][k],dis[j][v]+val+dis[u][k]);}}else{if(dis[x[i]][y[i]]==1e18) ans[++cnt]=-1;else ans[++cnt]=dis[x[i]][y[i]];}}per(i,cnt,1) printf("%lld\n",ans[i]);return 0;
}