fork download 
  1. #include <cstdio>
  2. #include <set>
  3. #include <utility>
  4. #include <vector>
  5. #include <tuple>
  6. #include <queue>
  7. #include <unordered_map>
  8.  
  9. using namespace std;
  10. typedef tuple <int, int, int> T;
  11.  
  12. int main()
  13. {
  14. 	int v, e, i, j, k, t, d = 0, cost = 0, pcost = 0X7FFFFFFF;
  15. 	scanf("%d %d", &v, &e);
  16. 	vector<unordered_map<int, int>> graph(v + 1);
  17. 	vector<unordered_map<int, bool>> inc(v + 1);
  18. 	vector<int> parent(v + 1);
  19. 	vector<int> depth(v + 1);
  20. 	priority_queue<T, vector<T>, greater<T>> edge;
  21.  
  22. 	for (i = 0; i < e; i++)
  23. 	{
  24. 		scanf("%d %d %d", &j, &k, &t);
  25. 		graph[j].insert(pair<int, int>(k, t));
  26. 		graph[k].insert(pair<int, int>(j, t));
  27. 		inc[j].insert(pair<int, bool>(k, false));
  28. 		inc[k].insert(pair<int, bool>(j, false));
  29. 	}
  30.  
  31. 	auto iter = graph[1].begin();
  32. 	for (; iter != graph[1].end(); iter++)
  33. 		edge.push(tuple<int, int, int>(iter->second, 1, iter->first));
  34. 	parent[1] = -1;
  35.  
  36. 	for (i = 1; i < v; i++)
  37. 	{
  38. 		while (true)
  39. 		{
  40. 			if (edge.empty())
  41. 			{
  42. 				printf("-1");
  43. 				return 0;
  44. 			}
  45. 			T ed = edge.top();
  46. 			edge.pop();
  47. 			if (parent[get<2>(ed)] == 0)
  48. 			{
  49. 				cost += get<0>(ed);
  50. 				parent[get<2>(ed)] = get<1>(ed);
  51. 				depth[get<2>(ed)] = depth[get<1>(ed)] + 1;
  52. 				inc[get<1>(ed)][get<2>(ed)] = true;
  53. 				inc[get<2>(ed)][get<1>(ed)] = true;
  54.  
  55. 				for (iter = graph[get<2>(ed)].begin(); iter != graph[get<2>(ed)].end(); iter++)
  56. 				{
  57. 					if (parent[iter->first] == 0)
  58. 						edge.push(tuple<int, int, int>(iter->second, get<2>(ed), iter->first));
  59. 				}
  60. 				break;
  61. 			}
  62. 		}
  63. 	}
  64.  
  65. 	for (i = 1; i < v; i++)
  66. 	{
  67. 		for (iter = graph[i].begin(); iter != graph[i].end(); iter++)
  68. 		{
  69. 			if (i > iter->first || inc[i][iter->first])
  70. 				continue;
  71.  
  72. 			int cursor1 = i, cursor2 = iter->first;
  73. 			while (cursor1 != cursor2)
  74. 			{
  75. 				if (depth[cursor1] > depth[cursor2])
  76. 				{
  77. 					if (iter->second - graph[cursor1][parent[cursor1]] < pcost && iter->second - graph[cursor1][parent[cursor1]] > 0)
  78. 						pcost = iter->second - graph[cursor1][parent[cursor1]];
  79. 					cursor1 = parent[cursor1];
  80. 				}
  81. 				else
  82. 				{
  83. 					if (iter->second - graph[cursor2][parent[cursor2]] < pcost && iter->second - graph[cursor2][parent[cursor2]] > 0)
  84. 						pcost = iter->second - graph[cursor2][parent[cursor2]];
  85. 					cursor2 = parent[cursor2];
  86. 				}
  87. 			}
  88. 		}
  89. 	}
  90.  
  91. 	if (pcost == 0X7FFFFFFF)
  92. 		printf("-1");
  93. 	else
  94. 		printf("%d", cost + pcost);
  95. }
Success #stdin #stdout 0s 4400KB
comments (?)
stdin 
7 12
1 2 8
1 3 5
2 3 10
2 4 2
2 5 18
3 4 3
3 6 16
4 5 12
4 6 30
4 7 14
5 7 4
6 7 26
stdout 
44
https://ideone.com/V0d43n
language:
C++14 (gcc 8.3)
created:
6 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!