ens-ulm-1

commit 053aafb22056b62bfe69d15f5e752d1366d972cb
parent 3ca2b376a74ffcaa0f2e8310c84d3c6c2232f15b
Author: Jachiet Louis <louis@jachiet.com>
Date:   Sat,  5 Apr 2014 13:54:46 +0200

Ajout du fichier de distance

Diffstat:
contest/louis/algo.cpp
 | 
24
++++++++++++++++++++++++
contest/louis/dist.gz
 | 
0

contest/louis/louis.cpp
 | 
50
+++++++++++++++++++++++++++++---------------------

3 files changed, 53 insertions(+), 21 deletions(-)
diff --git a/contest/louis/algo.cpp b/contest/louis/algo.cpp
@@ -0,0 +1,24 @@
+#include "louis.cpp"
+
+int main()
+{
+  lecture_entree();
+  vector<int> chem[8];
+  for( int i = 0 ; i < 8 ; i++)
+    {
+      int arrivee = s_depart ;
+      int l = 0 ;
+      chem[i].push_back(s_depart);
+      while( l < t_autorise )
+	{
+	  while(chem[i].back() == arrivee)
+	    arrivee = rand()%n_sommets ;
+	  int nouv = go_to(chem[i].back(),arrivee);
+	  l+= cout[id_arete[make_pair(chem[i].back(),nouv)]] ;
+	  if(l<t_autorise)
+	    chem[i].push_back(go_to(chem[i].back(),arrivee));
+	  //	  fprintf(stderr,"%d %d %d\n",i,chem[i].back(),arrivee);
+	}
+    }
+  affiche_sortie(chem);
+}
diff --git a/contest/louis/dist.gz b/contest/louis/dist.gz
Binary files differ.
diff --git a/contest/louis/louis.cpp b/contest/louis/louis.cpp
@@ -18,35 +18,43 @@ int go_to( int depart, int arrivee)
   if(!init)
     {
       init = 1 ;
-      fill(use[0],use[N_SOMMETS_MAJ],-1);
+      FILE * f = fopen("dist","rb");
+      fread(use,sizeof(use),1,f);
+      fclose(f);
     }
   if(use[depart][depart] == -1)
-    return use[depart][arrivee] ;
-  fill(cur_dist,cur_dist+N_SOMMETS_MAJ,INF);
-  priority_queue<pair<int,int> > todo ;
-  use[depart][depart] = depart ;
-  todo.push(make_pair(0,depart));
-  while(!todo.empty())
     {
-      pair<int,int> t = todo.top();
-      todo.pop();
-      t.first *= -1 ;
-      if(t.first == cur_dist[t.second])
+      fill(cur_dist,cur_dist+N_SOMMETS_MAJ,INF);
+      priority_queue<pair<int,int> > todo ;
+      use[depart][depart] = depart ;
+      todo.push(make_pair(0,depart));
+      cur_dist[depart] = 0 ;
+      while(!todo.empty())
 	{
-	  for(int v : adj[t.second] )
+	  pair<int,int> t = todo.top();
+	  todo.pop();
+	  t.first *= -1 ;
+	  if(t.first == cur_dist[t.second])
 	    {
-	      const int nouv_dist = t.first + longueur[id_arete[make_pair(t.first,v)]];
-	      if( nouv_dist != cur_dist[v] )
+	      for(int v : adj[t.second] )
 		{
-		  if(t.first)
-		    use[depart][v] = v ;
-		  else
-		    use[depart][v] = use[depart][t.first] ;
-
-		  cur_dist[v] = nouv_dist ;
-		  todo.push(make_pair(-nouv_dist,v));
+		  const int nouv_dist = t.first + longueur[id_arete[make_pair(t.second,v)]];
+		  if( nouv_dist < cur_dist[v] )
+		    {
+		      if(t.second == depart)
+			use[depart][v] = v ;
+		      else
+			use[depart][v] = use[depart][t.second] ;
+		      
+		      cur_dist[v] = nouv_dist ;
+		      todo.push(make_pair(-nouv_dist,v));
+		    }
 		}
 	    }
 	}
     }
+  if(use[depart][arrivee] == -1)
+    fprintf(stderr,"ERREUR !\n");
+  return use[depart][arrivee] ;
+
 }