fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int INF = 1e9;
  4. const int N = 35;
  5. int n;
  6. int c[N][N];
  7. bool visited[N];
  8. int choose[N];
  9. int minc = INF;
  10. int curc = 0;
  11. int min_edge[N];
  12. int total_min_edge = 0;
  13. vector<vector<int>> all_answers;
  14. void dq(int id) {
  15.     int lb = curc + total_min_edge;
  16.     if (lb > minc)
  17.         return;
  18.     for (int j = 2; j <= n; j++) {
  19.         if (!visited[j]) {
  20.             if (curc + c[choose[id - 1]][j] + (total_min_edge - min_edge[choose[id - 1]]) <= minc) {
  21.                 choose[id] = j;
  22.                 visited[j] = true;
  23.                 curc += c[choose[id - 1]][j];
  24.                 total_min_edge -= min_edge[choose[id - 1]];
  25.                 if (id == n) {
  26.                     int final_cost = curc + c[choose[n]][1];
  27.                     if (final_cost < minc) {
  28.                         minc = final_cost;
  29.                         all_answers.clear();
  30.                         vector<int> path(choose + 1, choose + n + 1);
  31.                         all_answers.push_back(path);
  32.                     }
  33.                     else if (final_cost == minc) {
  34.                         vector<int> path(choose + 1, choose + n + 1);
  35.                         all_answers.push_back(path);
  36.                     }
  37.                 }
  38.                 else {
  39.                     dq(id + 1);
  40.                 }
  41.  
  42.                 total_min_edge += min_edge[choose[id - 1]];
  43.                 curc -= c[choose[id - 1]][j];
  44.                 visited[j] = false;
  45.             }
  46.         }
  47.     }
  48. }
  49. int main() {
  50.     cin >> n ;
  51.     for (int i = 1; i <= n; i++) {
  52.         min_edge[i] = INF;
  53.         for (int j = 1; j <= n; j++) {
  54.             cin >> c[i][j];
  55.             if (j != i && c[i][j] < min_edge[i])
  56.                 min_edge[i] = c[i][j];
  57.         }
  58.         total_min_edge += min_edge[i];
  59.     }
  60.     choose[1] = 1;
  61.     visited[1] = true;
  62.     dq(2);
  63.     if (all_answers.size() == 1) {
  64.         cout << minc << endl ;
  65.         for (int i = 0; i < n; i++) {
  66.             cout << all_answers[0][i] << " " ;
  67.         }
  68.         cout << endl ;
  69.     }
  70.     else if (all_answers.size() > 1) {
  71.         cout << minc << " " << all_answers.size() << endl ;
  72.         for (const auto& path : all_answers) {
  73.             for (int i = 0; i < n; i++) {
  74.                 cout << path[i] << " " ;
  75.             }
  76.             cout << endl ;
  77.         }
  78.     }
  79. }
  80.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MJxzQS
language:
C++14 (gcc 8.3)
created:
6 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!