可以倍增floyd，倍增判断走2^i步是否存在负环就好了。
其实和3763是一样的，然而那题数据挂了。
#include<cstdio>
inline void upd1(int&a,int b){
a>b?a=b:0;
}
const int N=301;
typedef int arr[N][N];
int n;
void pre(arr a){
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
a[i][j]=1e9;
}
void dup(arr a,arr b){
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
a[i][j]=b[i][j];
}
bool jud(arr a){
for(int i=1;i<=n;++i)
if(a[i][i]<0)return 1;
return 0;
}
arr c,g,f[9];
void mul(arr a,arr b){
pre(c);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
for(int k=1;k<=n;++k)
upd1(c[i][k],a[i][j]+b[j][k]);
}
int m,u,v,w,s,l;
int main(){
scanf("%d%d",&n,&m);
pre(f[0]);
for(int i=1;i<=n;++i)
f[0][i][i]=0;
while(m--){
scanf("%d%d%d",&u,&v,&w);
f[0][u][v]=w;
}
for(s=1;;++s){
mul(f[s-1],f[s-1]);
if(jud(c))break;
if(1<<s>=n)
return!~puts("0");
dup(f[s],c);
}
dup(g,f[--s]),l=1<<s;
while(s){
mul(g,f[--s]);
if(!jud(c))
dup(g,c),l|=1<<s;
}
printf("%d
",l+1);
}