请求撤下所有spfa,spfa死了

这道题目是图论+二分答案，而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