ens-ulm-1

google hashcode 2014 source for team ens-ulm-1
git clone https://a3nm.net/git/ens-ulm-1/
Log | Files | Refs

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