这道题目是图论+二分答案，而spfa的极限复杂度是$O(nmlogn)$，显然是错的

通过网上随便找的卡spfa数据生成器（加上我修改成符合题目的输入），spfa挂了，本地DEV 10s+

#include <bits/stdc++.h>
using namespace std;
struct edge
{
  int u, v, w;
};
vector<edge>v;
int id[5000][5000],n=100,tp,m=10000/n,a[1000000];
int r()
{
	return rand();
}
int main()
{
	freopen("spfa1.in","w",stdout);
	srand(time(0));
	for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j)
	id[i][j]=++tp,a[tp]=tp;
	int SIZE=29989;
	for(int i=1;i<=n;++i)
	for(int j=1;j<=m;++j)
	{
		if(i<n)
		{
			v.push_back(edge{id[i][j],id[i+1][j],1});
			v.push_back(edge{id[i+1][j],id[i][j],1});
			if(j<m)
			{
				if(1)
				v.push_back(edge{id[i][j],id[i+1][j+1],r()%SIZE+10});
			else v.push_back(edge{id[i+1][j+1],id[i][j],r()%SIZE+10});
			}
		}
		if(j<m)
		{
			v.push_back(edge{id[i][j],id[i][j+1],r()%SIZE+10});
			v.push_back(edge{id[i][j+1],id[i][j],r()%SIZE+10});
		}
	}
	fprintf(stderr,"[%d,%d,%d]",v.size(),n,m);
	random_shuffle(v.begin(),v.end());
	printf("%d %d 1000000000\n",tp,v.size());
	for(int i=1;i<=tp;i++)
	if(i==1||i==tp)
	printf("%d ",1);
else if(i==2)
	printf("%d ",1000000000);
else printf("%d ",i);
	printf("\n");
	for(int i=0;i<v.size();++i)
	printf("%d %d %d\n",a[v[i].u],a[v[i].v],v[i].w);
}

@WYXkk