柯哀萌新在线求条入门水题

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define int long long

using namespace std;

const int N = 5005, M = 10000005, INF = INT_MAX;

int n, m;
int g[N][N], f[N][N], op[M], x[M], y[M], tmp[M];
int res[N];

void upd(int k)
{
	for (int i = 1; i <= n; i ++ )
	  for (int j = 1; j <= n; j ++ )
	    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}

signed main()
{
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
    scanf("%lld%lld", &n, &m);
    for (int i = 1; i <= n; i ++ )
      for (int j = 1; j <= n; j ++ )
      	 scanf("%lld", &f[i][j]);
	
	for (int i = 1; i <= m; i ++ )
	{
		scanf("%lld%lld%lld", &op[i], &x[i], &y[i]);
		if (op[i] == 1)
		{
			g[x[i]][y[i]] ++ ;
			tmp[i] = f[x[i]][y[i]];
			f[x[i]][y[i]] = INF;
		}
	}
	
	for (int k = 1; k <= n; k ++ )
	  for (int i = 1; i <= n; i ++ )
	    for (int j = 1; j <= n; j ++ )
	      f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
	
	for (int i = m; i >= 1; i -- )
	{
		if (op[i] == 1)
		{
			g[x[i]][y[i]] -- ;
			if (g[x[i]][y[i]]>0) continue;
			f[x[i]][y[i]] = min(f[x[i]][y[i]], tmp[i]);
			upd(x[i]);
			upd(y[i]);
		}
		else
		{
			if (f[x[i]][y[i]] >= INF) res[ ++ res[0]] = -1;
			else res[++ res[0]] = f[x[i]][y[i]];
		}
	}
	for (int i = res[0]; i >= 1; i -- ) printf("%lld\n", res[i]);
	return 0;
}