旅程

考虑删边比较难做，于是倒过来加边。

首先先做一遍 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;
}