• API
• FAQ
• Tools
• Archive
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();
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.

Top