fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. struct edge {
  7. 	int u, v, c;
  8. 	edge(int u, int v, int c) :
  9. 			u(u), v(v), c(c) {
  10. 	}
  11. 	bool operator<(const edge &e) const {
  12. 		return c < e.c;
  13. 	}
  14. };
  15.  
  16. const int N = 15, oo = 1e9;
  17. int n, m, k, g[N][N], dp[1 << N][N], iv[N], p[N];
  18. vector<edge> e;
  19.  
  20. int find(int x) {
  21. 	if (x == p[x])
  22. 		return x;
  23. 	return p[x] = find(p[x]);
  24. }
  25.  
  26. int MST() {
  27. 	sort(e.begin(), e.end());
  28. 	for (int i = 0; i < n; ++i)
  29. 		p[i] = i;
  30. 	int res = 0;
  31. 	for (int i = 0; i < m; ++i) {
  32. 		int u = find(e[i].u);
  33. 		int v = find(e[i].v);
  34. 		if (u != v) {
  35. 			res += e[i].c;
  36. 			p[u] = v;
  37. 		}
  38. 	}
  39. 	return res;
  40. }
  41.  
  42. int main(int argc, char **argv) {
  43. 	int T;
  44. 	scanf("%d", &T);
  45. 	while (T-- != 0) {
  46. 		scanf("%d%d%d", &n, &m, &k);
  47. 		for (int i = 0; i < n; ++i) {
  48. 			fill(g[i], g[i] + n, oo);
  49. 			g[i][i] = 0;
  50. 		}
  51. 		e.clear();
  52. 		int u, v, c;
  53. 		for (int i = 0; i < m; ++i) {
  54. 			scanf("%d%d%d", &u, &v, &c);
  55. 			--u, --v;
  56. 			g[u][v] = g[v][u] = c;
  57. 			e.push_back(edge(u, v, c));
  58. 		}
  59. 		for (int i = 0; i < k; ++i) {
  60. 			scanf("%d", &iv[i]);
  61. 			--iv[i];
  62. 		}
  63. 		if (k <= 1) {
  64. 			puts("0");
  65. 			continue;
  66. 		}
  67. 		if (n == k) {
  68. 			printf("%d\n", MST());
  69. 			continue;
  70. 		}
  71. 		for (int k = 0; k < n; ++k)
  72. 			for (int i = 0; i < n; ++i)
  73. 				for (int j = 0; j < n; ++j)
  74. 					g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
  75. 		for (int i = 0; i < k; ++i)
  76. 			for (int j = 0; j < n; ++j)
  77. 				dp[1 << i][j] = g[iv[i]][j];
  78. 		for (int mask = 1; mask < 1 << k; mask++) {
  79. 			if (((mask - 1) & mask) == 0)
  80. 				continue;
  81. 			for (int i = 0; i < n; ++i) {
  82. 				dp[mask][i] = oo;
  83. 				for (int pMask = (mask - 1) & mask; pMask > 0; pMask = (pMask - 1) & mask)
  84. 					dp[mask][i] = min(dp[mask][i], dp[pMask][i] + dp[mask ^ pMask][i]);
  85. 			}
  86. 			for (int i = 0; i < n; ++i)
  87. 				for (int j = 0; j < n; ++j)
  88. 					dp[mask][i] = min(dp[mask][i], dp[mask][j] + g[j][i]);
  89. 		}
  90. 		printf("%d\n", dp[(1 << k) - 1][iv[0]]);
  91. 	}
  92. 	return 0;
  93. }
Success #stdin #stdout 0s 4292KB
comments (?)
stdin
copy 
3
3 3 3
1 2 3
1 3 7
2 3 5
1 2 3
3 3 3
1 2 3
1 3 3
2 3 5
1 2 3
3 3 2
1 2 3
1 3 7
2 3 2
1 3
stdout
copy 
8
6
5
https://ideone.com/uXfZUV
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!