我直接分层图 spfa 跑的，折半优化了一下，就最优解第二了。

复杂度是我也不知道，而且我也不会卡，但是肯定是可以卡的。有没有仙人帮我卡一下/dk

#include<bits/stdc++.h>
using namespace std;
int n,k,hd,tl,q[3005],mp[305][305],x[90005],y[90005],ans[90005],d[3005],dd[3005],p[3005];
vector<pair<int,int> >e[3005],ee[3005];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&mp[i][j]);
	for(int i=1;i<=n*n;i++)
		scanf("%d%d",&x[i],&y[i]);
	memset(d,0x3f,sizeof(d));
	d[1]=0;
	memset(dd,0x3f,sizeof(dd));
	dd[((k+1)/2+1)*n]=0;
	for(int i=n*n;i>=1;i--){
		ans[i]=1061109567;
		for(int j=1;j<=n;j++)
			ans[i]=min(ans[i],d[k/2*n+j]+dd[j]);
		hd=1,tl=0;
		for(int j=0;j<=(k+1)/2;j++){
			int yy=(j+1)*n+y[i],xx=j*n+x[i];
			if(d[yy]>d[xx]+mp[x[i]][y[i]]){
				d[yy]=d[xx]+mp[x[i]][y[i]];
				if(p[yy]==0){
					p[yy]=1;
					q[++tl]=yy;
				}
			}
			e[xx].push_back(make_pair(yy,mp[x[i]][y[i]]));
		}
		while(hd<=tl){
			int x=q[hd];
			hd++;
			p[x]=0;
			for(auto i:e[x]){
				int y=i.first,z=i.second;
				if(d[y]>d[x]+z){
					d[y]=d[x]+z;
					if(p[y]==0){
						p[y]=1;
						q[++tl]=y;
					}
				}
			}
		}
		hd=1,tl=0;
		for(int j=0;j<=(k+1)/2;j++){
			int xx=(j+1)*n+y[i],yy=j*n+x[i];
			if(dd[yy]>dd[xx]+mp[x[i]][y[i]]){
				dd[yy]=dd[xx]+mp[x[i]][y[i]];
				if(p[yy]==0){
					p[yy]=1;
					q[++tl]=yy;
				}
			}
			ee[xx].push_back(make_pair(yy,mp[x[i]][y[i]]));
		}
		while(hd<=tl){
			int x=q[hd];
			hd++;
			p[x]=0;
			for(auto i:ee[x]){
				int y=i.first,z=i.second;
				if(dd[y]>dd[x]+z){
					dd[y]=dd[x]+z;
					if(p[y]==0){
						p[y]=1;
						q[++tl]=y;
					}
				}
			}
		}
	}
	for(int i=1;i<=n*n;i++)
		if(ans[i]!=1061109567)printf("%d\n",ans[i]);
		else puts("-1");
	return 0;
}