旅程
考虑删边比较难做，于是倒过来加边。
首先先做一遍 Floyd，然后每次加一条边，用这一条来更新，类似于 Bellman-ford，如果更新 \(i,j\)，用边 \((x,y)\)，则可写作 \(dis_{i,j}=dis_{i,x}+dis_{y,j}+w_{i,j}\)，也可以先更新所有点到 \(x\) 的距离，然后再更新 \(y\)。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
const int N=100010,M=210;
int n,m,mp[M][M],dis[M][M],ans[N],tot;
struct OP{
int c,x,y;
}op[N];
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
E(i, n)
E(j, n)scanf("%d",&mp[i][j]),dis[i][j]=mp[i][j];
E(i, m){
int c,x,y;
scanf("%d%d%d",&c,&x,&y);
op[i]={c,x,y};
// scanf("%d%d%d",&op[i].c,&op[i].x,&op[i].y);
if(c==1)dis[x][y]=1e9;
}
E(k, n)
E(i, n)
E(j, n)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
// E(i, n)
// E(j, n)printf("dis[%d][%d]=%d\n",i,j,dis[i][j]);
Re(i, m, 1){
int c=op[i].c,x=op[i].x,y=op[i].y;
if(c==1){
E(i, n)
E(j, n)dis[i][j]=min(dis[i][j],dis[i][x]+dis[y][j]+mp[x][y]);
}
else ans[++tot]=dis[x][y];
}
Re(i, tot, 1)printf("%d\n",ans[i]==1e9?-1:ans[i]);
return 0;
}