fork download
copy 
  1. //1005
  2. #include<iostream>
  3. #include<vector>
  4.  
  5. void FindConstructionTime(int* timeOfConstruction, std::vector<int> order[], 
  6.                           const int to, const int from, const int* time)
  7. {
  8. 	if (to != -1)
  9. 	{
  10.         //find max
  11. 		timeOfConstruction[from] =
  12. 			timeOfConstruction[from] > timeOfConstruction[to] + time[from] ?
  13. 			timeOfConstruction[from] : timeOfConstruction[to] + time[from];
  14. 	}
  15. 	else // 최종 건물 W의 경우
  16. 	{
  17. 		timeOfConstruction[from] = time[from];
  18. 	}
  19.  
  20. 	while (order[from].empty() == false)
  21. 	{
  22. 		FindConstructionTime(timeOfConstruction, order, 
  23.                              from, order[from].back(), time);
  24. 		order[from].pop_back();
  25. 	}
  26. }
  27. int main()
  28. {
  29. 	int t;
  30. 	scanf("%d", &t);
  31. 	for (int tc = 0; tc < t; tc++)
  32. 	{
  33. 		//입력--------------------------
  34.         int n, k;
  35. 		scanf("%d %d", &n, &k);
  36. 		int* time = new int[n];
  37. 		int* timeOfConstruction = new int[n];
  38. 		for (int i = 0; i < n; i++)
  39. 		{
  40. 			scanf("%d", &time[i]);
  41. 			timeOfConstruction[i] = 0;
  42. 		}
  43.  
  44. 		std::vector<int> order[1001];
  45.  
  46. 		for (int i = 0; i < k; i++)
  47. 		{
  48. 			int from, to;
  49. 			scanf("%d %d", &from, &to);
  50. 			from--;
  51. 			to--;
  52. 			order[to].push_back(from);
  53. 		}
  54. 		int w;
  55. 		scanf("%d", &w);
  56. 		w--;
  57. 		//건축시간 계산----------------------
  58.         FindConstructionTime(timeOfConstruction, order, -1, w, time);
  59.  
  60.         //최종 건축시간 중 critical pass를 찾는다. 
  61.         int max = 0;
  62. 		for (int i = 0; i < n; i++)
  63. 		{
  64. 			if (max < timeOfConstruction[i])
  65. 			{
  66. 				max = timeOfConstruction[i];
  67. 			}
  68. 		}
  69. 		printf("%d\n", max);
  70.  
  71.         if (time) delete time;
  72. 		if (timeOfConstruction) delete timeOfConstruction;
  73. 	}
  74. 	return 0;
  75. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
1
5 5
1 1 2 1 1
1 2
2 3
2 4
3 5
4 5
5
stdout
copy 
4
https://ideone.com/Q4uv1R
language:
C++14 (gcc 8.3)
created:
5 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!