fork download
copy 
  1. #include <iostream>
  2. #include <ctime>
  3. #include <stdlib.h>
  4.  
  5. using namespace std;
  6. const int infinity = 100000000;
  7. typedef int vector;
  8. vector metric(vector a, vector b){
  9.     if (a == b)
  10.         return infinity;
  11.     return (a < b) ? b - a : a - b;
  12. }
  13.  
  14. vector vertices[10];
  15. int graph[10][10] = {0};
  16. int stats[10 + 1] = {0};
  17. bool muteces[10] = {0};
  18.  
  19.  
  20.  
  21. int minimum = infinity;
  22. int cur_begin;
  23.  
  24.  
  25. int Prolong(int target_vertix, int sum, int starting_vertix, int step = 0){
  26.     if (sum > minimum){
  27.         ++stats[step];
  28.         return infinity;
  29.     }
  30.  
  31.     if (step == 9)
  32.         return sum + graph[target_vertix][starting_vertix]; 
  33.     int best_result = infinity;
  34.     for (int i = 0; i < 10; ++i){
  35.         if (muteces[i] != true && graph[target_vertix][i] != infinity){
  36.             muteces[i] = true;
  37.  
  38.             int tmp = Prolong(i, sum + graph[target_vertix][i], starting_vertix, step + 1);
  39.             muteces[i] = false;
  40.             if (tmp < best_result)
  41.                 best_result = tmp;
  42.         }
  43.     }
  44.  
  45.     if (best_result < minimum)
  46.         minimum = best_result;
  47.     return minimum;
  48. }
  49. int Solve(){
  50.     muteces[0] = true;
  51.     int res = Prolong(0, 0, 0);
  52.     muteces[0] = false;
  53.     for (int i = 1; i < 10; ++i){
  54.  
  55.         muteces[i] = true;
  56.         int tmp = Prolong(i, 0, i);
  57.         muteces[i] = false;
  58.         if (tmp < res)
  59.             res = tmp;
  60.     }
  61.     return res;
  62. }
  63.  
  64.  
  65. int main(){
  66.  
  67.     srand(time(NULL));
  68.     for (int i = 0; i < 10; ++i)
  69.         vertices[i] = rand() % 1007;
  70.  
  71.     for (int i = 0; i < 10; ++i)
  72.         for (int j = 0; j < 10; ++j)
  73.             graph[i][j] = metric(vertices[i],vertices[j]);
  74.     cout << Solve() << endl;
  75.     for (int i = 0; i < 10; ++i)
  76.         cout << stats[i] << endl;
  77.     return 0;
  78.  
  79. }
Success #stdin #stdout 0.04s 3296KB
comments (?)
stdin
copy 
1111
stdout
copy 
1860
0
0
0
250
4579
37089
151626
313781
316306
123080
https://ideone.com/EgfcUO
language:
C++ (gcc 8.3)
created:
11 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!