ens-ulm-1

commit 4d92775d31f1e93d94ba8561e8841366ee404f89
parent 5ca972807b1015724c6956f6369156b40e43acd2
Author: Jachiet Louis <louis@jachiet.com>
Date:   Sat,  5 Apr 2014 12:55:18 +0200

prepull commit

Diffstat:
contest/louis/main.cc
 | 
52
+++++++++++++++++++++++++++++++++++++++++++++-------
contest/louis/solution.h
 | 
1
-
contest/mc/lecture.cpp
 | 
4
++--

3 files changed, 47 insertions(+), 10 deletions(-)
diff --git a/contest/louis/main.cc b/contest/louis/main.cc
@@ -2,19 +2,57 @@
 #include <algorithm>
 #include <future>
 #include <vector>
-#include "solution.h"
+#include <queue>
 
 using namespace std;
 
-const int nbVoitures = 8 ;
-const int nbSommets = 11348 ;
-const int nbArcs = 17958 ;
-const int nbSecondes = 54000 ;
-const int depart = 4516 ;
+
+class louis
+{
+
+  const int nbVoitures = 8 ;
+  const int nbSommets = 11348 ;
+  const int nbArcs = 17958 ;
+  const int nbSecondes = 54000 ;
+  const int depart = 4516 ;
+  const int INF = 1000 * 1000 * 100 ;
+  vector<int> use[nbSommets] ;
+
+  // Renvoie la première intersection à utiliser
+  int go_to( int depart, int arrivee)
+  {
+    if(use[depart].size())
+      return use[depart][arrivee] ;
+    int cur_dist[nbSommets] ;
+    priority_queue<pair<int,int> > todo ;
+    todo.push(makepair(0,depart));
+    
+    fill(dist,dist+nbSommets,INF);
+    while(!todo.empty())
+      {
+	pair<int,int> t = todo.top();
+	todo.pop();
+	t.first *= -1 ;
+	if(t.first == cur_dist[t.second])
+	  {
+	    for(int v : get_vois(t.second) )
+	      {
+		const int nouv_dist = t.first + get_dist(t.first,v);
+		if( nouv_dist != cur_dist[v] )
+		  {
+		    cur_dist[v] = nouv_dist ;
+		    todo.push(makepair(-nouv_dist,v));
+		  }
+	      }
+	  }
+      }
+  }
+
+
 
 
 int main()
 {
-    std::future<bool> fut = async (is_prime,444444443); 
+  std::future<bool> fut = async (is_prime,444444443); 
   return 0;
 }
diff --git a/contest/louis/solution.h b/contest/louis/solution.h
@@ -31,5 +31,4 @@ class solution
       }
     fclose(f);
   }
-    
 };
diff --git a/contest/mc/lecture.cpp b/contest/mc/lecture.cpp
@@ -24,7 +24,7 @@ bool dbsens[N_ARETES_MAJ];//rue a double sens
 int couts[N_ARETES_MAJ];//cout(temps)
 int longueurs[N_ARETES_MAJ];//longueur
 
-vector<vector<int> > adj(N_SOMMETS_MAJ); // matrice d'adjacence
+vector<int> adj[N_SOMMETS_MAJ]; // matrice d'adjacence
 
 
 
@@ -33,7 +33,7 @@ struct dest{
   int cout;
   int longueur;
 };
-vector<vector<dest> > adj2(N_SOMMETS_MAJ); // matrice d'adjacence
+vector<dest> adj2[N_SOMMETS_MAJ]; // matrice d'adjacence