题解 [ABC375F] Road Blocked
cjh20090318
·
·
题解
非常模板的最短路题。
题意
你需要依次执行 $Q$ 次操作：
- `1 i`：断开第 $i$ 条边。
- `2 x y` 查询 $x$ 到 $y$ 的最短路径长度，如果无法到达输出 $-1$。
保证无重边自环，第 $1$ 种操作不超过 $300$ 次。
## 分析
断开边不好做，可以离线下来逆序处理操作，这样就从断边变成了加边。
查询的是全源最短路，先使用 Floyd 求出任意两点间的最短路径长度。
在加边 $(u,v)$ 的时候，枚举两个点 $i,j$，最短路径有 $3$ 种情况：
- $i,j$ 的最短路径不经过这条边。
- 从 $i$ 走到 $u$，经过 $(u,v)$ 边后再从 $v$ 走到 $j$。
- 从 $i$ 走到 $v$，经过 $(v,u)$ 边后再从 $u$ 走到 $j$。
因为第一种操作的数量不超过 $300$ 次，所以可以直接枚举两个端点取以上三种情况的最小值。
设 $Q_1$ 为第 $1$ 种操作次数，时间复杂度 $O(n^3 + Q_1n^2)$。
## 代码
```cpp
//the code is from chenjh
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int n,m,q;
struct Edge{
int u,v,w;
}e[300*300];
bool ct[300*300];//标记哪些边被砍掉了。
LL d[305][305];
struct QUE{
int op,x,y;
}Q[200005];
LL ans[200005];
void add(const int u,const int v,const LL&w){d[u][v]=min(d[u][v],w);}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
for(int i=1;i<=q;i++){
scanf("%d%d",&Q[i].op,&Q[i].x);
if(Q[i].op==2) scanf("%d",&Q[i].y);
else ct[Q[i].x]=1;//标记该边被断开。
}
memset(d,0x3f,sizeof d);//赋值无穷大。
for(int i=1;i<=n;i++) d[i][i]=0;
for(int i=1;i<=m;i++)if(!ct[i])
add(e[i].u,e[i].v,e[i].w),add(e[i].v,e[i].u,e[i].w);/添加未被断开的边。
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);//Floyd 求最短路，注意转移顺序 k,i,j。
for(int _=q,i;_>0;--_){//从后往前逆序处理操作。
if(Q[_].op==1){
i=Q[_].x,add(e[i].u,e[i].v,e[i].w),add(e[i].v,e[i].u,e[i].w);
for(int u=1;u<=n;u++)for(int v=1;v<=n;v++) d[u][v]=min({d[u][v],d[u][e[i].u]+e[i].w+d[e[i].v][v],d[u][e[i].v]+e[i].w+d[e[i].u][v]});//枚举端点，获得三种情况的最小值。
}
else ans[_]=d[Q[_].x][Q[_].y];//获得查询答案。
}
for(int _=1;_<=q;_++)if(Q[_].op==2) printf("%lld\n",ans[_]>=0x3f3f3f3f3f3f3f3fll?-1:ans[_]);//如果距离为无穷大即无法到达，输出 -1。
return 0;
}
```