想了个很神奇的做法，就是在 meet in the middle 的基础上暴力更新可能需要更新的路径。感觉要比 $O(n^4k)$ 要快些，但我只能证到这里。

using PII=std::pair<int,int>;
constexpr int N=3e2+5;
constexpr int inf=0x3f3f3f3f;
int a[N][N];
int d[2][N][11];//d[i][j][k] i:前半后半 j:哪个点 k:第几层
int from[2][N][11];//从哪个点继承最短
int n,K;
void spfa_first_half()
{
	static std::queue<PII>q;
	q.push({1,0});
	d[0][1][0]=0;
	while(q.size())
	{
		int x=q.front().first,dep=q.front().second;q.pop();
		for(int i=1;i<=n;i++)
		{
			if(a[x][i]==inf)
				continue;
			if(d[0][i][dep+1]>d[0][x][dep]+a[x][i])
			{
				from[0][i][dep+1]=x;
				d[0][i][dep+1]=d[0][x][dep]+a[x][i];
				if(dep+1<K/2)
					q.push({i,dep+1});
			}
		}
	}
}
void spfa_second_half()
{
	static std::queue<PII>q;
	q.push({n,K});
	d[1][n][K]=0;
	while(q.size())
	{
		int x=q.front().first,dep=q.front().second;q.pop();
		for(int i=1;i<=n;i++)
		{
			if(a[i][x]==inf)
				continue;
			if(d[1][i][dep-1]>d[1][x][dep]+a[i][x])
			{
				from[1][i][dep-1]=x;
				d[1][i][dep-1]=d[1][x][dep]+a[i][x];
				if(dep-1>K/2)
					q.push({i,dep-1});
			}
		}
	}
}
void reset_first_half(int x,int y,int k)//更新前半
{
	static std::queue<PII>q;
	if(from[0][y][k]==x)
	{
		from[0][y][k]=-1;
		q.push({y,k});
	}
	while(q.size())
	{
		int to=q.front().first,dep=q.front().second;
		q.pop();
		d[0][to][dep]=inf;
		for(int i=1;i<=n;i++)
		{
			if(dep+1<=K/2)
				if(from[0][i][dep+1]==to)
				{
					from[0][i][dep+1]=-1;
					q.push({i,dep+1});
				}
			if(a[i][to]==inf)
				continue;
			if(d[0][to][dep]>d[0][i][dep-1]+a[i][to])
			{
				from[0][to][dep]=i;
				d[0][to][dep]=d[0][i][dep-1]+a[i][to];
			}
		}
	}
}
void reset_second_half(int x,int y,int k)//更新后半
{
	static std::queue<PII>q;
	if(from[1][y][k]==x)
	{
		from[1][y][k]=-1;
		q.push({y,k});
	}
	while(q.size())
	{
		int to=q.front().first,dep=q.front().second;
		q.pop();
		d[1][to][dep]=inf;
		for(int i=1;i<=n;i++)
		{
			if(dep-1>=K/2)
				if(from[1][i][dep-1]==to)
				{
					from[1][i][dep-1]=-1;
					q.push({i,dep-1});
				}
			if(a[to][i]==inf)
				continue;
			if(d[1][to][dep]>d[1][i][dep+1]+a[to][i])
			{
				from[1][to][dep]=i;
				d[1][to][dep]=d[1][i][dep+1]+a[to][i];
			}
		}
	}
}
void reset_all(int x,int y)
{
	for(int i=1;i<=K/2;i++)
		reset_first_half(x,y,i);
	for(int i=K-1;i>=K/2;i--)
		reset_second_half(y,x,i);
}
int main()
{
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	memset(d,0x3f,sizeof(d));
	spfa_first_half();
	spfa_second_half();
	int T=n*n;
	while(T--)
	{
		int x,y;
		read(x,y);
		a[x][y]=inf;
		reset_all(x,y);
		int ans=inf;
		for(int i=1;i<=n;i++)
			if(d[0][i][K/2]!=inf&&d[1][i][K/2]!=inf)
				ans=min(d[0][i][K/2]+d[1][i][K/2],ans);
		printf("%d\n",ans);
	}
	return 0;
}