louis.cpp (3823B)
1 #include <cstdio> 2 #include <cstdlib> 3 #include <algorithm> 4 //#include <future> 5 #include <vector> 6 #include <queue> 7 #include "../mc/lecture.cpp" 8 using namespace std; 9 10 11 const int INF = 1000 * 1000 * 100 ; 12 short use[N_SOMMETS_MAJ][N_SOMMETS_MAJ] ; 13 int cur_dist[N_SOMMETS_MAJ] ; 14 void init_use() 15 { 16 const char *filename = "dist2"; 17 FILE * f = fopen(filename,"rb"); 18 if(!f) { 19 fprintf(stderr,"%s not found !\n", filename); 20 exit(1); 21 } 22 const int tr = sizeof(use); 23 int r = fread(use,1,tr,f); 24 if (r < tr) { 25 fprintf(stderr, "read only %d/%d bytes in %s\n", r, tr, filename); 26 exit(1); 27 } 28 fclose(f); 29 } 30 31 short nb_aretes[N_SOMMETS_MAJ][N_SOMMETS_MAJ]; 32 33 void calc_nb_aretes() { 34 fprintf(stderr, "Calculating nb_aretes for the first time, please wait\n"); 35 for (int i = 0; i < N_SOMMETS_MAJ; i++) { 36 for (int j = 0; j < N_SOMMETS_MAJ; j++) 37 nb_aretes[i][j] = N_SOMMETS_MAJ; 38 deque<int> cur; 39 nb_aretes[i][i] = 0; 40 cur.push_back(i); 41 while (!cur.empty()) { 42 int c = cur.front(); 43 int d = nb_aretes[i][c] + 1; 44 cur.pop_front(); 45 for (int k = 0; k < int(adj[c].size()); k++) { 46 int v = adj[c][k]; 47 if (nb_aretes[i][v] <= d) 48 continue; 49 nb_aretes[i][v] = d; 50 cur.push_back(v); 51 } 52 } 53 } 54 fprintf(stderr, "Done calculating nb_aretes\n"); 55 } 56 57 void init_nb_aretes() { 58 const char *filename = "nb_aretes.cache"; 59 FILE *f = fopen(filename, "rb"); 60 const int tr = sizeof(nb_aretes); 61 if (!f) { 62 calc_nb_aretes(); 63 f = fopen(filename, "wb"); 64 if(!f) { 65 fprintf(stderr,"%s not found !\n", filename); 66 exit(1); 67 } 68 fwrite(nb_aretes,1,tr,f); 69 fclose(f); 70 return; 71 } 72 int r = fread(nb_aretes,1,tr,f); 73 if (r < tr) { 74 fprintf(stderr, "read only %d/%d bytes in %s\n", r, tr, filename); 75 exit(1); 76 } 77 fclose(f); 78 } 79 // Renvoie la première intersection à utiliser 80 /* 81 int go_to( int depart, int arrivee) 82 { 83 if(!init) 84 { 85 init = 1 ; 86 } 87 if(use[depart][depart] == -1) 88 { 89 fill(cur_dist,cur_dist+N_SOMMETS_MAJ,INF); 90 priority_queue<pair<int,int> > todo ; 91 use[depart][depart] = depart ; 92 todo.push(make_pair(0,depart)); 93 cur_dist[depart] = 0 ; 94 while(!todo.empty()) 95 { 96 pair<int,int> t = todo.top(); 97 todo.pop(); 98 t.first *= -1 ; 99 if(t.first == cur_dist[t.second]) 100 { 101 for(int v : adj[t.second] ) 102 { 103 const int nouv_dist = t.first + longueur[id_arete[make_pair(t.second,v)]]; 104 if( nouv_dist < cur_dist[v] ) 105 { 106 if(t.second == depart) 107 use[depart][v] = v ; 108 else 109 use[depart][v] = use[depart][t.second] ; 110 111 cur_dist[v] = nouv_dist ; 112 todo.push(make_pair(-nouv_dist,v)); 113 } 114 } 115 } 116 } 117 } 118 if(use[depart][arrivee] == -1) 119 fprintf(stderr,"ERREUR !\n"); 120 return use[depart][arrivee] ; 121 } 122 */ 123 124 // Comme complete, mais préserve les arêtes existantes 125 vector<int> complete_preserve( vector<int> &c) { 126 vector<int> r ; 127 r.push_back(c[0]); 128 for(size_t i = 1 ; i < c.size() ; i++ ) { 129 if (id_arete[make_pair(c[i-1], c[i])]) 130 r.push_back(c[i]); 131 else 132 while (r.back() != c[i]) 133 r.push_back(use[r.back()][c[i]]); 134 } 135 return r ; 136 } 137 138 void complete_preserve(vector<int> sol[]) { 139 for (int v = 0; v < n_vehicules; v++) 140 sol[v] = complete_preserve(sol[v]); 141 } 142 143 vector<int> complete ( vector<int> & c) 144 { 145 vector<int> r ; 146 r.push_back(c[0]); 147 // fprintf(stderr,"complete : %d\n",r.back()); 148 for(size_t i = 1 ; i < c.size() ; i++ ) 149 { 150 while(r.back() != c[i]) { 151 //fprintf(stderr, "complete %zu/%zu -> %zu\t add %d\n", i, c.size(), r.size(), use[r.back()][c[i]]); 152 r.push_back(use[r.back()][c[i]]); 153 } 154 } 155 return r ; 156 } 157 158 void complete_all (vector<int> sol[]) 159 { 160 for (int v = 0; v < n_vehicules; v++) 161 sol[v] = complete(sol[v]); 162 } 163