fork download
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. const int N = 15;
  5. vector<pair<int,int> > g[N];
  6. int dp[(1<<N)+5], MSK;
  7.  
  8. int n, m, k;
  9. int calc(int msk) {
  10. if((msk&MSK) == MSK) return 0;
  11. int &ret = dp[msk];
  12. if(ret != -1) return ret;
  13. ret = 1e9;
  14. if(msk == 0) {
  15. for(int u=0; u<n; ++u)
  16. ret = min(ret, calc(1<<u));
  17. } else {
  18. for(int u=0; u<n; ++u)
  19. if((msk>>u)&1) {
  20. for(int i=0, v, c; i<g[u].size(); ++i) {
  21. v = g[u][i].first;
  22. c = g[u][i].second;
  23. if(!((msk>>v)&1))
  24. ret = min(ret, c + calc(msk | (1<<v)));
  25. }
  26. }
  27. }
  28. return ret;
  29. }
  30.  
  31. int main() {
  32. int t;
  33. scanf("%d", &t);
  34. while(t--) {
  35. scanf("%d%d%d", &n, &m, &k);
  36. for(int i=0; i<n; ++i)
  37. g[i].clear();
  38. for(int i=0, u, v, c; i<m; ++i) {
  39. scanf("%d%d%d", &u, &v, &c);
  40. --u, --v;
  41. g[u].push_back(make_pair(v, c));
  42. g[v].push_back(make_pair(u, c));
  43. }
  44. MSK = 0;
  45. for(int i=0, x; i<k; ++i) {
  46. scanf("%d", &x);
  47. --x;
  48. MSK |= (1<<x);
  49. }
  50. memset(dp, -1, sizeof dp);
  51. printf("%d\n", calc(0));
  52. }
  53. return 0;
  54. }
Success #stdin #stdout 0s 4384KB
stdin
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
8
6
5