fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 1e5 + 9;
  5.  
  6. /*
  7. Find the minimum cost connected tree where at least the important nodes are connected
  8. dp(x,i) = minimum cost of a tree rooted at i connecting the important node in bitmask x.
  9. Complexity: O(3^k * n + 2^k * m log m)
  10. */
  11.  
  12. int n, k, m;
  13. vector<int> imp;//k important nodes
  14. vector<pair<int, long long>> g[N];
  15. long long d[1000][N]; //[2^k][edge count]
  16. const long long inf = LLONG_MAX / 3;
  17. bool vis[N];
  18. long long MST() {
  19. 	for(int i = 0; i < (1 << k); i++) fill(d[i], d[i] + N, inf);
  20. 	for(int i = 0; i < k; ++i) {
  21. 		d[1 << i][imp[i]] = 0;
  22. 	}
  23. 	priority_queue<pair<long long, int>> q;
  24. 	for(int mask = 1; mask < (1 << k); ++mask) {
  25. 		for(int a = 0; a < mask; ++a) {
  26. 			int b = mask ^ a;
  27. 			if(b > a) continue;
  28. 			for(int v = 0; v < n; ++v) {
  29. 				d[mask][v] = min(d[mask][v], d[a][v] + d[b][v]);
  30. 			}
  31. 		}
  32. 		memset(vis, 0, sizeof vis);
  33. 		for(int v = 0; v < n; ++v) {
  34. 			if(d[mask][v] == inf) continue;
  35. 			q.emplace(-d[mask][v], v);
  36. 		}
  37.  
  38. 		while(!q.empty()) {
  39. 			long long cost = -q.top().first;
  40. 			int v = q.top().second;
  41. 			q.pop();
  42. 			if(vis[v]) continue;
  43. 			vis[v] = true;
  44. 			for(auto edge : g[v]) {
  45. 				long long ec = cost + edge.second;
  46. 				if(ec < d[mask][edge.first]) {
  47. 					d[mask][edge.first] = ec;
  48. 					q.emplace(-ec, edge.first);
  49. 				}
  50. 			}
  51. 		}
  52. 	}
  53.  
  54. 	long long res = inf;
  55. 	for(int v = 0; v < n; ++v) {
  56. 		res = min(res, d[(1 << k) - 1][v]);
  57. 	}
  58. 	return res;
  59. }
  60. int main() {
  61. 	ios_base::sync_with_stdio(0);
  62. 	cin.tie(0);
  63.  
  64. 	cin >> n >> k >> m;
  65. 	imp.resize(k);
  66. 	for(int i = 0; i < k; ++i) {
  67. 		cin >> imp[i];
  68. 		--imp[i];
  69. 	}
  70. 	for(int i = 0; i < m; ++i) {
  71. 		int u, v;
  72. 		long long w;
  73. 		cin >> u >> v >> w;
  74. 		--u;
  75. 		--v;
  76. 		g[u].emplace_back(v, w);
  77. 		g[v].emplace_back(u, w);
  78. 	}
  79. 	cout << MST() << '\n';
  80. 	return 0;
  81. }
  82.  
Success #stdin #stdout 0.01s 6852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3074457345618258602
https://ideone.com/WSK3D8
language:
C++ (gcc 8.3)
created:
75 days 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!