fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. int n;
  7. vector<int> vcost;
  8. vector<vector<pair<int, int> > > edges;
  9.  
  10. vector<pair<pair<int,int>, int> > order;
  11.  
  12. void dfs(int v, int p) {
  13. 	for (size_t j = 0; j < edges[v].size(); j++) {
  14. 		int w = edges[v][j].first;
  15. 		if (w == p) continue;
  16. 		order.push_back(make_pair(make_pair(w, v), edges[v][j].second));
  17. 		dfs(w, v);
  18. 	}
  19. }
  20.  
  21. vector<vector<pair<ll, int> > > best;
  22.  
  23. void prop_edge(int v, int w, int c) {
  24. 	// 保证两个末端不同
  25. 	for (int j = 0; j < 2; j++) {
  26. 		if (best[v][j].second == best[w][0].second) {
  27. 			swap(best[w][0], best[w][1]);
  28. 		}
  29. 		best[w][1] = min(best[w][1], make_pair(best[v][j].first + c, best[v][j].second));
  30. 		if (best[w][0] > best[w][1]) {
  31. 			swap(best[w][0], best[w][1]);
  32. 		}
  33. 	}
  34. }
  35.  
  36. int main() {
  37. 	ios::sync_with_stdio(0), cin.tie(0);
  38. 	cin >> n;
  39. 	vcost.resize(n);
  40. 	for (int i = 0; i < n; i++) cin >> vcost[i];
  41. 	edges.resize(n);
  42. 	for (int i = 0; i < n-1; i++) {
  43. 		int a, b, c;
  44. 		cin >> a >> b >> c;
  45. 		a--; b--;
  46. 		edges[a].push_back(make_pair(b, c));
  47. 		edges[b].push_back(make_pair(a, c));
  48. 	}
  49. 	order.reserve(n-1);
  50. 	dfs(0, -1);
  51.  
  52. 	ll total = 0;
  53. 	vector<vector<int> > cc_edges(n);
  54. 	vector<int> vis(n);
  55. 	vector<int> which_cc(n);
  56. 	vector<int> cc;
  57. 	cc.reserve(n);
  58. 	best.assign(n, vector<pair<ll, int> >(2));
  59. 	vector<pair<ll, int> > cc_best;
  60. 	cc_best.reserve(n);
  61. 	vector<vector<int> > ccs;
  62. 	ccs.reserve(n);
  63. 	while (true) {
  64. 		fill(vis.begin(), vis.end(), 0);
  65. 		fill(which_cc.begin(), which_cc.end(), -1);
  66. 		ccs.clear();
  67. 		for (int i = 0; i < n; i++) {
  68. 			if (vis[i]) continue;
  69. 			cc.clear();
  70. 			cc.push_back(i);
  71. 			vis[i] = 1;
  72. 			for (int s = 0; s < int(cc.size()); s++) {
  73. 				int v = cc[s];
  74. 				for (size_t j = 0; j < cc_edges[v].size(); j++) {
  75. 					int w = cc_edges[v][j];
  76. 					if (!vis[w]) {
  77. 						vis[w] = 1;
  78. 						cc.push_back(w);
  79. 					}
  80. 				}
  81. 			}
  82. 			for (size_t j = 0; j < cc.size(); j++) {
  83. 				which_cc[cc[j]] = int(ccs.size());
  84. 			}
  85. 			ccs.push_back(cc);
  86. 		}
  87. 		if (ccs.size() == 1) break;
  88. 		for (int v = 0; v < n; v++) {
  89. 			best[v][0] = make_pair(vcost[v], which_cc[v]);
  90. 			best[v][1] = make_pair(1e18, -1);
  91. 		}
  92. 		for (int i = n-2; i >= 0; i--) {
  93. 			pair<pair<int, int>, int>& e = order[i];
  94. 			prop_edge(e.first.first, e.first.second, e.second);
  95. 		}
  96. 		for (int i = 0; i < n-1; i++) {
  97. 			pair<pair<int, int>, int>& e = order[i];
  98. 			prop_edge(e.first.second, e.first.first, e.second);
  99. 		}
  100. 		cc_best.resize(ccs.size());
  101. 		fill(cc_best.begin(), cc_best.end(), make_pair(1e18, -1));
  102. 		for (int v = 0; v < n; v++) {
  103. 			for (int j = 0; j < 2; j++) {
  104. 				if (best[v][j].second != which_cc[v]) {
  105. 					cc_best[which_cc[v]] = min(cc_best[which_cc[v]], 
  106. 											   make_pair(best[v][j].first + vcost[v], best[v][j].second));
  107. 				}
  108. 			}
  109. 		}
  110. 		for (int k = 0; k < int(ccs.size()); k++) {
  111. 			int l = cc_best[k].second;
  112. 			if (cc_best[l].second == k && l < k) continue;
  113. 			total += cc_best[k].first;
  114. 			cc_edges[ccs[k].front()].push_back(ccs[l].front());
  115. 			cc_edges[ccs[l].front()].push_back(ccs[k].front());
  116. 		}
  117. 	}
  118. 	cout << total << '\n';
  119. }
  120.  
Success #stdin #stdout 0s 4484KB
comments (?)
stdin
copy 
6
44 23 31 29 32 15
1 2 10
1 3 12
1 4 16
4 5 8
4 6 15
stdout
copy 
359
https://ideone.com/Ww87yP
language:
C++ (gcc 8.3)
created:
4 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!