SHARE
TWEET

Untitled

a guest Oct 23rd, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<stream>
  2.  
  3. typedef {
  4.     int data[100];
  5.     int n;
  6. } Arr;
  7.  
  8. typedef {
  9.     int first[100];
  10.     int second[100];
  11.     int n;
  12. } PairArr;
  13.  
  14. Arr createArr(){ Arr arr; arr.n = 0; return arr }
  15. Arr createPairArr(){ PairArr arr; arr.n = 0; return arr }
  16.  
  17. Arr pushArr(Arr arr, int x){
  18.     arr.data[arr.n++] = x;
  19.     return arr;
  20. }
  21. Arr pushPairArr(PairArr arr, int first, int second){
  22.     arr.first[arr.n] = first;
  23.     arr.second[arr.n] = second;
  24.     arr.n++;
  25.     return arr;
  26. }
  27. int size(Arr arr){ return arr.n; }
  28. int size(PairArr arr){ return arr.n; }
  29. int indexOf(Arr arr, int x){
  30.     for(int i=0; i<size(arr); i++){
  31.         if(arr.data[i] == x) return i;
  32.     }
  33.     return -1;
  34. }
  35. int contains(Arr arr, int x){
  36.     return indexOf(arr, x) >= 0;
  37. }
  38.  
  39. typedef {
  40.     int M[100][100];
  41.     int n;
  42. } Metrix;
  43.  
  44. Metrix createMetrix(){ Metrix m; m.n = 0; return m; }
  45. Metrix addVertex(Metrix m){ m.n++; return m; }
  46. Metrix setPath(Metrix m, int from, int to, weight){
  47.     m.M[from][to] = weight;
  48.     return m;
  49. }
  50. int getWeight(Metrix m, int from, int to){
  51.     return m.M[from][to];
  52. }
  53. Arr getNexts(Metrix m, int from){
  54.     Arr next = createArr();
  55.     for(int i=0; i < m.n; i++){
  56.         if(from == i) continue;
  57.         if(m.M[from][i] == 0) continue;
  58.         arr = push_arr(arr, i);
  59.     }
  60.     return next;
  61. }
  62. PairArr getNextsGroup(Metrix m, Arr froms, Arr visited){
  63.     PairArr next = createPairArr();
  64.     for(int i=0; i < size(froms); i++){
  65.         Arr next2 = getNexts(m, froms.data[i]);
  66.         next2 = filterNotVisit(next2, visited);
  67.         for(int j=0; j<size(next2); j++){
  68.             next = pushPairArr(next, i, next2.data[j]);
  69.         }
  70.     }
  71.     return next;
  72. }
  73. Arr filterNotVisit(Arr next, Arr visited){
  74.     Arr next2 = createArr();
  75.     for(int i=0; i<size(next); i++){
  76.         if(contains(visited, next.data[i])) continue;
  77.         pushArr(next2, next.data[i]);
  78.     }
  79.     return next2;
  80. }
  81.  
  82. int main(){
  83.  
  84.     int n = 5;
  85.  
  86.     Metrix M = createMetrix();
  87.     M = addVertex(M);
  88.     M = addVertex(M);
  89.     M = addVertex(M);
  90.     M = addVertex(M);
  91.     M = setPath(M, 0, 1, 9);
  92.  
  93.     Arr visited = createArr();
  94.     visited = pushArr(visited, 0);
  95.  
  96.     PairArr path = createPairArr();
  97.  
  98.     for(int i=0; i<n - 1; i++){
  99.         PairArr nexts = getNextsGroup(M, visited, visited);
  100.         if(size(nexts) == 0) continue;
  101.         int from = nexts.first[0];
  102.         int to = nexts.second[0];
  103.         for(int j=1; j<size(nexts); j++){
  104.             if(getWeight(M,nexts.first[j], nexts.second[j]) < getWeight(M, from, to)){
  105.                 from = nexts.first[j];
  106.                 to = nexts.second[j];
  107.             }
  108.         }
  109.         path = pushPairArr(path, from, to);
  110.         visited = pushArr(visited, to);
  111.     }
  112.  
  113.     for(int i=0; i<size(path); i++){
  114.         cout << path.first[i] << " "<< path.second[i] << " " << getWeight(M,path.first[i], path.second[i]) << endl;
  115.     }
  116.  
  117.     return 0;
  118. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top