ens-ulm-1

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

mc.cpp (2390B)

      1 #include <ctime>
      2 #include <vector>
      3 #include <map>
      4 #include <set>
      5 #include <algorithm>
      6 #include <cstdio>
      7 
      8 #define N_SOMMETS_MAJ 12000
      9 #define N_ARETES_MAJ 18000
     10 
     11 using namespace std;
     12 
     13  int n_sommets;
     14  int n_aretes;
     15  int t_autorise;
     16  int n_vehicules;
     17  int depart;
     18 
     19 double longitudes[N_SOMMETS_MAJ];
     20 double latitudes[N_SOMMETS_MAJ];
     21 
     22 int departs[N_ARETES_MAJ];//depart
     23 int arrivees[N_ARETES_MAJ];//arrivee
     24 bool dbsens[N_ARETES_MAJ];//rue a double sens
     25 int couts[N_ARETES_MAJ];//cout(temps)
     26 int longueurs[N_ARETES_MAJ];//longueur
     27 
     28 vector<vector<int> > adj(N_SOMMETS_MAJ); // matrice d'adjacence
     29 
     30 
     31 
     32 struct dest{
     33   int arrivee;
     34   int cout;
     35   int longueur;
     36   int id_route;
     37 };
     38 vector<vector<dest> > adj2(N_SOMMETS_MAJ); // matrice d'adjacence
     39 
     40 
     41 
     42 
     43 void lecture_entree(){
     44   scanf("%d",&n_sommets);
     45   scanf("%d",&n_aretes);
     46   scanf("%d",&t_autorise);
     47   scanf("%d",&n_vehicules);
     48   scanf("%d",&depart);
     49   for(int i=0;i<n_sommets;i++)scanf("%lf %lf",&longitudes[i],&latitudes[i]);
     50   for(int i=0;i<n_aretes;i++){
     51     int x;
     52     scanf("%d %d %d %d %d",&departs[i],&arrivees[i],&x,&couts[i],&longueurs[i]);
     53     dbsens[i]=(x==2);
     54     adj[departs[i]].push_back(arrivees[i]); 
     55     if(dbsens[i])  adj[arrivees[i]].push_back(departs[i]);
     56     
     57     dest xx;
     58     xx.arrivee=arrivees[i];xx.cout=couts[i];xx.longueur=longueurs[i];
     59     xx.id_route=i;
     60     dest xx2;
     61     xx2.id_route=i;
     62     xx2.arrivee=departs[i];xx2.cout=couts[i];xx2.longueur=longueurs[i];
     63     adj2[departs[i]].push_back(xx); 
     64     if(dbsens[i])  adj2[arrivees[i]].push_back(xx2);
     65   }
     66 }
     67 
     68 
     69 
     70 
     71 int main(){
     72 srand(time(NULL));
     73 lecture_entree();
     74 
     75 printf("%d\n",n_vehicules);
     76 
     77 int sol_max=0;
     78 vector<int> best_solution;
     79 int N_TESTS=100;
     80 for(int A=0;A<N_TESTS;A++){
     81 
     82 int sol=0;
     83 vector<int> solution;
     84 
     85 for(int i=0;i<n_vehicules;i++){
     86   int t=0;
     87   int pt=depart;
     88   
     89   set<int> seen;
     90   vector<int> blah;
     91   blah.push_back(depart);
     92   while(true){
     93     int d=rand()%(adj[pt].size());
     94     if(t+adj2[pt][d].cout>t_autorise) break;
     95     t+=adj2[pt][d].cout;
     96     blah.push_back(adj2[pt][d].arrivee);
     97     pt=adj2[pt][d].arrivee;
     98     if(seen.find(adj2[pt][d].id_route) != seen.end()){seen.insert(adj2[pt][d].id_route);sol+=adj2[pt][d].longueur;}else printf("%d\n",adj2[pt][d].id_route);
     99   }
    100 
    101 //  printf("%d\n",blah.size());
    102 //  for(int i=0;i<blah.size();i++){printf("%d\n",blah[i]);}
    103 }
    104 printf("%d\n",sol);
    105 if(sol>sol_max){
    106   sol_max=sol;
    107   best_solution=solution;
    108 }
    109 
    110 
    111 }
    112 
    113 }
    114