Advertisement
Josif_tepe

Untitled

May 4th, 2022
791
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. using namespace std;
  5. vector<pair<int, int> > graph[105];
  6. int dp[20][1 << 20];
  7. int travelling_salesman(int node, int visited) {
  8.     if(__builtin_popcount(visited) == 1) {
  9.         for(int i = 0; i < graph[node].size(); i++) {
  10.             if(graph[node][i].first == 0) {
  11.                 return graph[node][i].second;
  12.             }
  13.         }
  14.         return 0;
  15.     }
  16.     if(node == 0 and visited == 0) {
  17.         return 0;
  18.     }
  19.     if(dp[node][visited] != -1) {
  20.         return dp[node][visited];
  21.     }
  22.     int new_mask = visited;
  23.     new_mask -= (1 << node);
  24.     int result = 2e9;
  25.     for(int i = 0; i < graph[node].size(); i++) {
  26.         int sosed = graph[node][i].first;
  27.         int weight = graph[node][i].second;
  28.         if(visited & (1 << sosed)) {
  29.             result = min(result, travelling_salesman(sosed, new_mask) + weight);
  30.         }
  31.     }
  32.    
  33.     return dp[node][visited] = result;
  34. }
  35. int main() {
  36.     int n, m;
  37.     cin >> n >> m;
  38.     memset(dp, -1, sizeof dp);
  39.     for(int i = 0; i < m; i++) {
  40.         int a, b, c;
  41.         cin >> a >> b >> c;
  42.         a--; b--;
  43.         graph[a].push_back(make_pair(b, c));
  44.         graph[b].push_back(make_pair(a, c));
  45.     }
  46.     int mask = (1 << (n)) - 1;
  47.     cout << travelling_salesman(0, mask) << endl;
  48.    
  49.     return 0;
  50. }
  51. /*
  52.  
  53.  4 6
  54.  1 2 10
  55.  2 4 25
  56.  2 3 35
  57.  3 4 30
  58.  3 1 15
  59.  4 1 20
  60.  
  61.  */
  62.  
Advertisement
RAW Paste Data Copied
Advertisement