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

## Re:floyd 也能过 重边考虑一下

Posted by sunjianzhao at 2019-09-24 22:58:43 on Problem 3259
In Reply To:floyd 也能过 重边考虑一下 Posted by:yuzhihao at 2019-07-20 18:52:36
```> #include<stdio.h>
> #include<string.h>
> #include<math.h>
> #include<algorithm>
> #define inf 0x3f3f3f3f
> using namespace std;
> int map[2005][2005]={0};
> int main()
> {
> 	int n,m,s;
> 	int t;
> 	scanf("%d",&t);
> 	getchar();
> 	while(t--)
> 	{
> 		scanf("%d%d%d",&n,&m,&s);
> //		printf("%d  %d  %d\n",n,m,s);
> 		for(int i=1;i<=n;i++)
> 		{
> 			map[i][i]=0;
> 			for(int j=1;j<=n;j++)
> 			{
> 				map[i][j]=inf;
> 			}
> 		}
> 		int u,v,w;
> 		for(int i=0;i<m;i++)
> 		{
> 			scanf("%d%d%d",&u,&v,&w);
> 			if(map[u][v]>w)
> 			map[u][v]=map[v][u]=w;
> 		}
> 		for(int i=0;i<s;i++)
> 		{
> 			scanf("%d%d%d",&u,&v,&w);
> 			map[u][v]=-w;
> 		}
>
> 		int flag=0;
> 		for(int k=1;k<=n;k++)
> 		{
> 			for(int i=1;i<=n;i++)
> 			{
> 				for(int j=1;j<=n;j++)
> 				{
> 					if(map[i][j]>map[i][k]+map[k][j])
> 						map[i][j]=map[i][k]+map[k][j];
> 				}
> 				if(map[i][i]<0)
> 				{
> 					flag=1;
> 					break;
> 				}
> 			}
> 			if(flag==1)
> 			break;
> 		}
> 		if(flag==1)
> 			printf("YES\n");
> 		else
> 			printf("NO\n");
> 	}
> }
```

Followed by: