fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <stdio.h>
  4.  
  5. int n,m,w,f,size,tmp;
  6. int d[1000];
  7.  
  8. const int INF = 1000000000;
  9.  
  10. struct Tedge{
  11. 	int a,b,c;
  12.  }  e[10000];
  13.  
  14. int main()
  15. {
  16. 	scanf("%d",&f);
  17. 	while(f--)
  18. 	{
  19. 		scanf("%d %d %d",&n,&m,&w);
  20. 		for(int i = 0; i <= n; i++) d[i] = 0;
  21. 		while(m--)
  22. 		{
  23. 			int ta,tb,tc;
  24. 			scanf("%d %d %d",&ta,&tb,&tc);
  25. 			e[size].a = ta;
  26. 			e[size].b = tb;
  27. 			e[size++].c = tc;
  28. 			e[size].a = tb;
  29. 			e[size].b = ta;
  30. 			e[size++].c = tc;
  31. 		}
  32.  
  33. 		while(w--)
  34. 		{
  35. 			int ta,tb,tc;
  36. 			scanf("%d %d %d",&ta,&tb,&tc);
  37. 			e[size].a = ta;
  38. 			e[size].b = tb;
  39. 			e[size++].c = -tc;// otric vremya na rebre
  40. 		}
  41. 		for (int i = 0; i < n ; i++) {
  42. 			tmp = -1;
  43. 			for (int j = 0; j < size; j++)
  44. 				if (d[e[j].b] > (d[e[j].a] + e[j].c)) {
  45. 					d[e[j].b] = std::max(-INF,d[e[j].a] + e[j].c);
  46. 					tmp = e[j].b;
  47. 				}
  48. 		}
  49. 		if(tmp == -1)
  50. 			printf("NO\n");
  51. 		else
  52. 			printf("YES\n");
  53. 		//f--;
  54. 	}
  55. 	return 0;
  56. }
Success #stdin #stdout 0.01s 5540KB
comments (?)
stdin
copy 
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
stdout
copy 
NO
YES
https://ideone.com/9K7zGO
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!