Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 这出题人太缺德了，floyd能过，n的数目不只是500

Posted by Mangata at 2020-07-05 14:06:35 on Problem 3259
```#include<cstdio>
#include<cstring>
#define maxn 2005
#define INF 0x3f3f3f3f
using namespace std;
int n,m,w,flag;
int mp[maxn][maxn];
void init()
{
for(int i=1;i<=n;++i)
{
mp[i][i]=0;
for(int j=1;j<=n;++j)
{
mp[i][j]=INF;
}
}
}
int floyd()
{
flag=0;
for(int k=1;k<=n;++k)
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(mp[i][j]>mp[i][k]+mp[k][j])
mp[i][j]=mp[i][k]+mp[k][j];
}
if(mp[i][i]<0)
{
flag=1;
goto out;
}
}
}
out:
return flag;
}
int main(void)
{
int T;
scanf("%d",&T);
while(T--)
{
int s,e,t;
scanf("%d%d%d",&n,&m,&w);
init();
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&s,&e,&t);
if(mp[s][e]>t)
mp[s][e]=mp[e][s]=t;
}
for(int i=1;i<=w;++i)
{
scanf("%d%d%d",&s,&e,&t);
mp[s][e]=-t;
}
if(floyd())
puts("YES");
else
puts("NO");

}
return 0;
}```

Followed by: