ens-ulm-1

commit 0a47ec4047cc8af7f4964237dda6ad9b5b7d3b9d
parent 1637c7d79df159a2076f2f496ace41259e1de4c5
Author: Jachiet Louis <louis@jachiet.com>
Date:   Sat,  5 Apr 2014 13:08:51 +0200

Ajout de plus court chemin

Diffstat:
contest/louis/louis.cpp
 | 
61
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
contest/louis/main.cc
 | 
58
----------------------------------------------------------

2 files changed, 61 insertions(+), 58 deletions(-)
diff --git a/contest/louis/louis.cpp b/contest/louis/louis.cpp
@@ -0,0 +1,61 @@
+#include <cstdio>
+#include <algorithm>
+#include <future>
+#include <vector>
+#include <queue>
+
+using namespace std;
+
+
+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 ;
+  short use[nbSommets][nbSommets] ;
+  int cur_dist[nbSommets] ;
+
+  louis()
+  {
+    fill(use[0],use[nbSommets],-1);
+  }
+
+  // Renvoie la première intersection à utiliser
+  int go_to( int depart, int arrivee)
+  {
+    if(use[depart][depart] == -1)
+      return use[depart][arrivee] ;
+    fill(cur_dist,cur_dist+nbSommets,INF);
+    priority_queue<pair<int,int> > todo ;
+    use[depart][depart] = depart ;
+    todo.push(makepair(0,depart));
+    use[depart]
+    while(!todo.empty())
+      {
+	pair<int,int> t = todo.top();
+	todo.pop();
+	t.first *= -1 ;
+	if(t.first == cur_dist[t.second])
+	  {
+	    for(int v : adj[t.second] )
+	      {
+		const int nouv_dist = t.first + longueur[id_arete[make_pair(t.first)]];
+		if( nouv_dist != cur_dist[v] )
+		  {
+		    if(t.first)
+		      use[depart][v] = v ;
+		    else
+		      use[depart][v] = use[depart][t.first] ;
+
+		    cur_dist[v] = nouv_dist ;
+		    todo.push(makepair(-nouv_dist,v));
+		  }
+	      }
+	  }
+      }
+  }
+};
diff --git a/contest/louis/main.cc b/contest/louis/main.cc
@@ -1,58 +0,0 @@
-#include <cstdio>
-#include <algorithm>
-#include <future>
-#include <vector>
-#include <queue>
-
-using namespace std;
-
-
-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); 
-  return 0;
-}