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[maxn][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[0][0], &dp[0][0] + (maxn)*(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.  
  34.     // th co so
  35.     FOR(i, 1, n) {
  36.         int mask = (1 << (i - 1));
  37.         dp[i][mask] = 0;
  38.     }
  39.  
  40.  
  41.  
  42.     FOR(mask, 1, (1 << n) - 1) {
  43.         FOR(i, 1, n) {
  44.             if (bit(mask, i - 1) == 0) continue;
  45.  
  46.             FOR(j, 1, n) {
  47.                 if (bit(mask, j - 1) == 1) continue;
  48.  
  49.                 int next_mask = mask | (1 << (j - 1));
  50.                 dp[j][next_mask] = min(dp[j][next_mask], dp[i][mask] + cost[i][j]);
  51.  
  52.             }
  53.         }
  54.     }
  55.  
  56.  
  57.  
  58.     int res = 1e9;
  59.     for (int i = 1; i <= n; ++i) {
  60.         res = min(res, dp[i][(1 << n) - 1]);
  61.     }
  62.  
  63.     cout << res;
  64.  
  65.  
  66.     return 0;
  67. }
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/FjOc39
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!