fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
  5. #define bit(mask, i) (((mask) >> (i)) & 1)
  6.  
  7.  
  8. const int maxn = 11;
  9.  
  10.  
  11. int n, m;
  12. int cost[maxn][maxn];
  13. int dp[1 << maxn];
  14.  
  15.  
  16.  
  17. signed main() {
  18.     ios::sync_with_stdio(0);
  19.     cin.tie(0); cout.tie(0);
  20.  
  21.     cin >> n >> m;
  22.  
  23.     fill(&cost[0][0], &cost[0][0] + maxn*maxn, 1e9);
  24.     fill(dp, dp + (1 << maxn), 1e9);
  25.  
  26.  
  27.     for (int i = 1; i <= m; ++i) {
  28.         int u, v, w; cin >> u >> v >> w;
  29.  
  30.         cost[u][v] = cost[v][u] = min(cost[u][v], w);
  31.     }
  32.  
  33.     // th co so
  34.     FOR(i, 1, n) {
  35.         int mask = (1 << (i - 1));
  36.         dp[mask] = 0;
  37.     }
  38.  
  39.  
  40.     FOR(mask, 1, (1 << n) - 1) {
  41.         FOR(i, 1, n) {
  42.             if (bit(mask, i - 1) == 0) continue;
  43.  
  44.             FOR(j, 1, n) {
  45.                 if (bit(mask, j - 1) == 1) continue;
  46.  
  47.                 dp[mask ^ (1 << (j - 1))] = min(dp[mask ^ (1 << (j - 1))], dp[mask] + cost[i][j]);
  48.             }
  49.         }
  50.     }
  51.  
  52.     cout << dp[(1 << n) - 1];
  53.  
  54.  
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4 4
1 2 4
2 3 5
2 4 2
3 4 1
stdout
copy 
7
https://ideone.com/jHLvLX
language:
C++14 (gcc 8.3)
created:
43 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!