fork download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <set>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. const int INF = 1000000000;
  9.  
  10. int N, M;
  11. int A[100];
  12. int g[100][100];
  13. int a, b, c;
  14.  
  15. int dp[1024][20];
  16.  
  17. int main() {
  18.  
  19.     cin >> N >> M;
  20.     for (int i = 0; i < M; i++) {
  21.         cin >> a >> b >> c;
  22.         g[a][b] = c;
  23.         g[b][a] = c;
  24.     }
  25.  
  26.     for (int i = 0; i < (1<<N); i++) {
  27.         for (int j = 0; j < N; j++) {
  28.             dp[i][j] = INF;
  29.         }
  30.     }
  31.  
  32.     dp[0][0] = 0;
  33.     for (int mask = 0; mask < (1<<N); mask++) {
  34.         for (int i = 0; i < N; i++) {
  35.             if (dp[mask][i] == INF) continue;
  36.             for (int j = 0; j < N; j++) {
  37.                 if ((mask & (1 << j)) == 0) {
  38.                     dp[mask | (1<<j)][j] = min(dp[mask | (1<<j)][j], dp[mask][i] + g[i][j]);
  39.                 }
  40.             }
  41.         }
  42.  
  43.     }
  44.     cout << dp[(1<<N)-1][0] << endl;
  45.  
  46.  
  47.  
  48.     return 0;
  49. }
Success #stdin #stdout 0.01s 5524KB
comments (?)
stdin
copy 
7 8
1 3 1
1 4 1
3 7 1
7 4 1
7 5 1
6 7 1
5 2 1
6 2 1
stdout
copy 
0
https://ideone.com/OaPj6s
language:
C++ (gcc 8.3)
created:
2 years 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!