prune.cpp (1439B)
1 #include <cstdio> 2 #include <algorithm> 3 #include <vector> 4 #include <queue> 5 using namespace std; 6 7 8 // essaie d'identifier et de raccourcir les morceaux inutiles de trajet 9 void prune(vector<int> trajectoires[], vector<int> resultat[]) { 10 vector<int> order; 11 for (int i=0; i<8; i++) 12 order.push_back(i); 13 random_shuffle(order.begin(), order.end()); 14 15 bitset<N_ARETES_MAJ> aretes; 16 17 for (int i=0; i< n_vehicules; i++) { 18 int v = order[i]; 19 int skipped_last = 0; 20 // push first point 21 resultat[v].push_back(trajectoires[v][0]); 22 for (int j=0; j< int(trajectoires[v].size() - 1); j++) { 23 pair<int, int> p = make_pair(trajectoires[v][j], trajectoires[v][j+1]); 24 int a = id_arete[p]; 25 if (!a) { 26 fprintf(stderr, "ERREUR"); 27 return; 28 } 29 if (!aretes[a]) { 30 aretes[a] = 1; 31 if (skipped_last) { 32 // je dois dire la précédente aussi 33 resultat[v].push_back(trajectoires[v][j]); 34 } 35 // j'ai passe une arete utile de j à j+1, donc je dis j+1 36 resultat[v].push_back(trajectoires[v][j+1]); 37 // je n'ai plus rien skip 38 skipped_last = 0; 39 } else { 40 // c'est inutile, donc je ne dis pas j+1 41 // je le note 42 skipped_last = 1; 43 } 44 } 45 } 46 } 47 48 void prune_in_place(vector<int> sol[]) { 49 vector<int> tmp[n_vehicules]; 50 prune(sol, tmp); 51 for (int v = 0; v < n_vehicules; v++) 52 sol[v] = tmp[v]; 53 }