ens-ulm-1

commit 63b3e263110a19ec69e6c8ad6e9fb2af5c382fe8
parent e55d18c95811cc27d14f880aa67adfcb31c8302c
Author: Jachiet Louis <louis@jachiet.com>
Date:   Sat,  5 Apr 2014 13:14:06 +0200

Merge branch 'master' of gitorious.org:ens-ulm-1/ens-ulm-1

Diffstat:
contest/mc/lecture.cpp
 | 
33
++++++++++++++++++++++++++++++++-
contest/mc/mc2.cpp
 | 
38
++++++++++++++++++++++++++++++++++++++

2 files changed, 70 insertions(+), 1 deletion(-)
diff --git a/contest/mc/lecture.cpp b/contest/mc/lecture.cpp
@@ -3,6 +3,7 @@
 #include <map>
 #include <algorithm>
 #include <cstdio>
+#include <string.h>
 
 #define N_SOMMETS_MAJ 12000
 #define N_ARETES_MAJ 18000
@@ -39,6 +40,36 @@ void affiche_sortie(vector<int> trajectoires[]) {
   }
 }
 
+// format: score, temps1, temps2, ..., temps8
+// (ou vide si solution invalide)
+vector<int> evalue_solution(vector<int> trajectoires[]) {
+  bool aretes[N_ARETES_MAJ];
+  memset(aretes, 0, sizeof(aretes));
+  vector<int> resultat;
+  resultat.push_back(0);
+  
+  int score = 0;
+  for (int i=0; i< n_vehicules; i++) {
+    int temps = 0;
+    for (int j=0; j< trajectoires[i].size() - 1; j++) {
+      pair<int, int> p = make_pair(trajectoires[i][j], trajectoires[i][j+1]);
+      int a = id_arete[p];
+      if (!a) {
+        resultat.clear();
+        return resultat;
+      }
+      if (!aretes[a]) {
+        score += longueur[a];
+        aretes[a] = 1;
+      }
+      temps += cout[a];
+    }
+    resultat.push_back(temps);
+  }
+  resultat[0] = score;
+  return resultat;
+}
+
 void lecture_entree(){
   scanf("%d",&n_sommets);
   scanf("%d",&n_aretes);
@@ -46,7 +77,7 @@ void lecture_entree(){
   scanf("%d",&n_vehicules);
   scanf("%d",&s_depart);
   for(int i=0;i<n_sommets;i++)scanf("%lf %lf",&longitudes[i],&latitudes[i]);
-  for(int i=0;i<n_aretes;i++){
+  for(int i=1;i<=n_aretes;i++){
     int x;
     scanf("%d %d %d %d %d",&depart[i],&arrivee[i],&x,&cout[i],&longueur[i]);
     dbsens[i]=(x==2);
diff --git a/contest/mc/mc2.cpp b/contest/mc/mc2.cpp
@@ -0,0 +1,38 @@
+#include "lecture.cpp"
+
+vector<int> sortie[8];
+
+
+
+void completion_hasard(int t, int i){
+  int pt=sortie[i][sortie[i].size()-1];
+ while(true){
+   int d=rand()%(adj[pt].size());
+   int ar=id_arete[make_pair(pt,adj[pt][d])];
+   if(t+cout[ar]>t_autorise) break;
+   t+=cout[ar];
+   sortie[i].push_back(adj[pt][d]);
+   pt=adj[pt][d];
+ }
+  
+}
+
+
+ 
+int main(){
+srand(time(NULL));
+lecture_entree();
+
+printf("%d\n",n_vehicules);
+for(int i=0;i<n_vehicules;i++){
+
+  int pt=s_depart;
+  sortie[i].push_back(s_depart);
+  completion_hasard(0,i);
+   
+
+ printf("%d\n",sortie[i].size());
+ for(int j=0;j<sortie[i].size();j++){printf("%d\n",sortie[i][j]);}
+}
+}
+