题解：
网上还有一种spfa+深度限制的算法
https://www.cnblogs.com/BearChild/p/6624302.html
是不加队列优化的spfa，我觉得复杂度上限是bellman-ford nm的，另外从每个点跑加上二分答案所以是n^2mlogn的
但实测的确是挺快的，可能是深度限制的原因
这题可以用倍增floyd
比较慢的就是二分+倍增floyd是n^3log^2n的
可以直接用找lca的思想，做到n^3logn
不太懂floyd的理论
两个矩阵算起来的时候要用新矩阵去更新的
c[i][j]=min(c[i][j],a[i][k]+b[k][j])这样做
然后卡了一下常（指针）
不过在bz上效果好像不是很明显
自己测试还是很明显得
不过windos下数组极慢，要用5.5s
linux下只用了2s，指针的win和linux下几乎相同都是1s
代码：
#include <bits/stdc++.h>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (rint i=h;i<=t;i++)
#define dep(i,t,h) for (rint i=t;i>=h;i--)
const int INF=1e9;
const int N=;
char ss[<<],*A=ss,*B=ss;
IL char gc()
{
return (A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++);
}
template<class T>void read(T &x)
{
rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=c^;
while (c=gc(),<c&&c<) x=(x<<)+(x<<)+(c^); x*=f;
}
int f[][N][N],t[N][N],t1[N][N],n,m;
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
read(n); read(m);
rep(k,,)
rep(i,,n)
rep(j,,n)
if (i!=j)
f[k][i][j]=INF;
rep(i,,m)
{
int x,y,z;
read(x); read(y); read(z);
if (f[][x][y]>z) f[][x][y]=z;
}
rep(i,,)
{
rep(i1,,n)
rep(i2,,n)
{
rint tmp=f[i-][i2][i1];
rint *p1=f[i-][i1];
rep(i3,,n)
{
rint *p3=f[i][i2];
rint p4=p3[i3];
rint p2=tmp+p1[i3];
if (p4>p2) p3[i3]=p2;
}
}
}
rep(i,,n)
rep(j,,n)
t[i][j]=f[][i][j];
int ans=;
dep(i,,)
{
rep(i1,,n)
rep(i2,,n)
t1[i1][i2]=INF;
rep(i1,,n)
{
rint (*g)=f[i][i1];
rep(i2,,n)
{
rint tmp=t[i2][i1];
rint *p3=t1[i2];
rep(i3,,n)
{
rint p1=p3[i3];
rint p2=tmp+g[i3];
if (p1>p2) p3[i3]=p2;
}
}
}
bool tt=;
rep(j,,n)
if (t1[j][j]<) tt=;
if (!tt)
{
ans+=<<i;
memcpy(t,t1,sizeof(t1));
}
}
if (ans+==) cout<<<<endl;
else cout<<ans+<<endl;
return ;
}