10986 - Sending email

//el problema no es más que un simple dijkstra, sólo no hay que leer con cin las aristas

#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <sstream>
using namespace std;
#define inf 1000000

void leer(int&a){
 scanf("%d",&a);
}

int main(){
 int test;
 cin>>test;


 for(int tt=1;tt<=test;tt++){
  int n,m,s,t;
  cin>>n>>m>>s>>t;
 
  vector<vector<int> > adj(n);//adyacencia de vértices
  vector<vector<int> > wadj(n);//los pesos de las aristas, este vector es inyectivo a adj
  int a,b,c;
  
  for(int i=0;i<m;i++){
   leer(a);
   leer(b);
   leer(c);
   adj[a].push_back(b);
   adj[b].push_back(a);
   wadj[a].push_back(c);
   wadj[b].push_back(c);
  }
 
  vector<int> dist(n,inf);
  dist[s]=0;
  typedef pair<int,int> pii;
 
  priority_queue<pii,vector<pii>,greater<pii> > q;
  q.push(make_pair(0,s));
  int res=-1;
 
  while(!q.empty()){
   int v=q.top().second;
   int d=q.top().first;
   q.pop();
   if(dist[v]<d) continue;
   if(v==t){res=d;break;}
  
   for(int i=0;i<adj[v].size();i++){
     int u=adj[v][i];
     int nd=wadj[v][i]+d;
     if(nd<dist[u]){
      dist[u]=nd;
      q.push(make_pair(nd,u));
     }
   }
  }
 
  cout<<"Case #"<<tt<<": ";
  if(res==-1) cout<<"unreachable"<<endl;
  else cout<<res<<endl;
 }
}

10801 - Lift Hopping

 //la solución es hacer un dijkstra, intentando todas las posibilidades
// en cada piso, intentamos ir a todos los otros posibles pisos sin verificar //nada

#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <sstream>
using namespace std;
#define inf 1000000

int main(){
 int n,k;
 while(cin>>n>>k){
    vector<int> time(n);//la velocidad de cada elevador
    for(int i=0;i<n;i++) cin>>time[i];
  
    vector<vector<int> > elev(n);//este arreglo contiene todos los pisos accesables por el elevador i
    vector<vector<int> > flo(100);//este arreglo contiene todos los elevadores que paran en el piso i
    string cad;
      getline(cin,cad); //para corregir la linea vacia
    
    //se llenan todas las adyacencias
    for(int i=0;i<n;i++){
    
      getline(cin,cad);
      istringstream is(cad);
      int x;
      while(is>>x){
    elev[i].push_back(x);
    flo[x].push_back(i);
      }
    }
  
    //soluciones
    vector<int> sol(100,inf);
    sol[0]=0;
  
    //estado: tiempo,piso
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater< pair<int,int> > > q;
    q.push(make_pair(0,0));
    int res=-1;
  
    while(!q.empty()){
     int fl=q.top().second;//piso actual
     int tim=q.top().first;//tiempo actual
     q.pop();
     if(tim>sol[fl]) continue;//si este estado no tiene sentido
     if(fl==k){res=tim;break;}//si se llegó a la solución
   
     for(int i=0;i<flo[fl].size();i++){
      int el=flo[fl][i];//elevador que llega al piso fl
    
      for(int j=0;j<elev[el].size();j++){ //se intenta ir a todos los pisos accesables por este elevador, no se hace ninguna verificacion
    int next=elev[el][j]; //siguiente piso
    int ntime=tim+60+abs(next-fl)*time[el]; //nuevo tiempo
    //ojo que el primer elevador que tomemos no tendrá penalidad de tiempo, eso lo vemos en el output
    if(sol[next]>ntime){//si se relaja
      sol[next]=ntime;
      q.push(make_pair(ntime,next));
    }
      }
    
     }
    }
  
    if(res==-1) cout<<"IMPOSSIBLE"<<endl;
    else cout<<(k!=0?res-60:0)<<endl;//si k!=0, entonces, corregimos el tiempo por la penalidad que le pusimos al primer elevador

 }
}

10099 The Tourist Guide

/*
La solución se basa en la relajación max min para el maximum bottleneck problem
Se asume como elemento neutro de max a 0 y al elemento neutro de min como inf para
que son un bellman ford se resuelva esto en O(VE)
*/


#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
  int N,R;
  int test=1;
 
  while(cin>>N>>R && N){
   vector<pair<int,int> > edg(R);//aristas
   vector<int> cap(R);//capacidades
  
   for(int i=0;i<R;i++){
    cin>>edg[i].first>>edg[i].second;
    cin>>cap[i];
    edg[i].first--;
    edg[i].second--;
   }
   int s,d,p;
   cin>>s>>d>>p;
   s--;d--;
   #define inf 1000000
   vector<int> sol(N,0);
   sol[s]=inf;
  
   for(int i=0;i<N-1;i++){
    //las aristas son bidireccionales
    for(int j=0;j<R;j++){
     int u=edg[j].first;
     int v=edg[j].second;
     int w=cap[j];
     int a=min(sol[u],w);
     int b=min(sol[v],w);
     if(b>sol[u]) sol[u]=b;
     if(a>sol[v]) sol[v]=a;
    }
   }
  
   cout<<"Scenario #"<<test++<<endl;
   int cant=sol[d]-1;//podemos llevar una persona menos que sol[d], ya que debemos viajar en el carro
   cout<<"Minimum Number of Trips = "<<(p+cant-1)/cant<<endl<<endl;
  }
}

658 - It's not a Bug, it's a Feature!

//la solución es simplemente un dijkstra, en tanto que dado un estado
//(tiempo y bugs activos) se trata de ir a todos los otros posibles estados
//por medio de los patchs dados, con bitwise, si no, sale TLE

#include <vector>
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define mp make_pair


int main(){
 int n,m;
 int best[1<<20];//arreglo donde se guardarán las mejores soluciones, recordar que para n bugs, hay 1<<n=2^n posibles estados
 int test=1;//número de test
 char aux;

 while(cin>>n>>m && n!=0){
  int completo=(1<<n)-1;//n bits en 1
 
  //respectivamente para el patch i: inhas = lo que debe tener previamente | innhas = lo que no debe tener previamente |
  //outadd= lo que se añade | outrest=lo que se quita
  vector<int> inhas(m,0),innhas(m,0),outadd(m,0),outrest(m,completo);
 
  vector<int> t(m); //los tiempos de cada patsh
 
  //lectura
  for(int i=0;i<m;i++){
    cin>>t[i];
    for(int j=0;j<n;j++){
     cin>>aux;
     if(aux=='-') innhas[i]|=1<<j;
     else if(aux=='+') inhas[i]|=1<<j;
    }
   
    for(int j=0;j<n;j++){
     cin>>aux;
     if(aux=='+') outadd[i]|=1<<j;
     else if(aux=='-') outrest[i]&=~(1<<j);
    }
  }
 
  memset(best,-1,4*(1<<n));//se pone todo el espacio necesario en 1, se multiplica por 4 porque cada int son 4 bytes
  // y metset copia una cantidad de bytes
 
  int ini=completo;
  best[ini]=0;//estado inicial
 
  //estado de la cola de prioridad, un par: <tiempo acumulado, estado actual>
  priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
  q.push(mp(0,ini));//se añade estado inicial
  int res=-1;
 
  while(!q.empty()){
    int cost=q.top().first;
    int state=q.top().second;
    q.pop();
   
    if(best[state]<cost) continue; //si este vértice es basura
    if(state==0){res=cost;break;} //si es solución
     
    //se intenta con todos los patchs
    for(int i=0;i<m;i++){
     //se verifica si el path i sirve
     bool puede=true;
     if((state&inhas[i])!=inhas[i]) puede=false;
     else if((state&innhas[i])!=0) puede=false;
    
     if(puede){
      //se crea el siguiente estado
      int next=state;
      next|=outadd[i];
      next&=outrest[i];
      int ncost=cost+t[i];
      //si el nuevo estado se relaja
      if(best[next]==-1||best[next]>ncost){
    best[next]=ncost;
    q.push(mp(ncost,next));
      }
     }
    }
  }
 
  cout<<"Product "<<test++<<endl;
  if(res!=-1) cout<<"Fastest sequence takes "<<res<<" seconds."<<endl;
  else cout<<"Bugs cannot be fixed."<<endl;
  cout<<endl;
 }
}

10369 - Arctic Network

// Básicamente, es hacer una búsqueda binaria sobre todas las posibles
// distancias D, y para cada una de estas distancias calcular la cantidad de
// componentes conexos que quedan luego de intentar hacer un MST
// y según esta cantidad y la cantidad de satélites disponibles, verificar
// si cierto D cumple o no

#include
#include
#include
#include
#include
#include
using namespace std;

int p[500],rank[500];

void make_set(int x){
    p[x]=x;
   rank[x]=0;
}
void link(int x,int y){
    if(rank[x]&gt;rank[y])
        p[y]=x;
    else{
        p[x]=y;
        if(rank[x]==rank[y]){
            rank[y]++;
        }
    }
}
int find_set(int x){
    if(x!=p[x]){
        p[x]=find_set(p[x]);
    }
    return p[x];
}
void Union(int x,int y){
    link(find_set(x),find_set(y));
}


int S,P;
pair pp[500];
vector<pair<double,pair<int,int> > > edg;

bool cumple(double D){
  for(int i=0;i 
  int sz=edg.size();
  for(int i=0;i
   double w=edg[i].first;
   int u=edg[i].second.first;
   int v=edg[i].second.second;
   if(find_set(u)!=find_set(v)){
      if( w<D) Union(u,v);
      else break;
   }
  }
  set ss;
  for(int i=0;i  sz=ss.size();
  if(sz==1) return true;
  if(sz&lt;=S) return true;
  else return false;
}

double solve(){
 double izq=0;
 double der=1e10;
 while(fabs(der-izq)&gt;1e-05){
  double mid=(izq+der)/2;
  if(cumple(mid)) der=mid;
  else izq=mid;
 }
 return (izq+der)/2;
}

int main(){
 int N;
 cin&gt;&gt;N;
 for(int tt=0;tt
   cin&gt;&gt;S&gt;&gt;P;
  
   for(int i=0;i&gt;pp[i].first&gt;&gt;pp[i].second;
   edg.resize(0);
   for(int i=0;i     int dx=pp[i].first-pp[j].first;
     int dy=pp[i].second-pp[j].second;
     double d=sqrt(dx*dx+dy*dy);
    edg.push_back(make_pair(d,make_pair(i,j)));
   }
   sort(edg.begin(),edg.end());
   double ret=solve();
   printf("%.2lf\n",ret);
 }
}

567 - Risk

//no más que un simple floyd warshall para responder queries

#include
#include
#include
#include
#include
using namespace std;

int main(){
  int m[20][20];
  int r,x,tt=1;
  while(cin>>r){
  
   for(int i=0;i<20;i++) for(int j=0;j<20;j++) m[i][j]=i!=j?1000000:0;
   
   for(int i=0;i<19;i++){
    if(i>0) cin>>r;
    for(int j=0;j>x;m[i][x-1]=m[x-1][i]=1;}
   }
   int n=20;
  
   for(int k=0;k  
   cin>>r;
   cout<<"Test Set #"<<
   for(int i=0;i
    int a,b;
    cin>>a>>b;
    printf("%2d to %2d:%2d\n",a,b,m[a-1][b-1]);
   }
   cout<
  }
}

10397 - Connect the Campus

//es una variación del kruskal, con aristas ya preestablecidas

#include
#include
#include
#include
#include
using namespace std;

int p[750],rank[750];
//union find

void make_set(int x){
    p[x]=x;
   rank[x]=0;
}
void link(int x,int y){
    if(rank[x]>rank[y])
        p[y]=x;
    else{
        p[x]=y;
        if(rank[x]==rank[y]){
            rank[y]++;
        }
    }
}
int find_set(int x){
    if(x!=p[x]){
        p[x]=find_set(p[x]);
    }
    return p[x];
}
void Union(int x,int y){
    link(find_set(x),find_set(y));
}

bool comp(pair > A,pair > B){
 return A.first
}

int main(){
  int n;
  while(cin>>n){
      double d;
      vector > > edg;
      for(int i=0;i
    
      vector > pp(n);
    
      for(int i=0;i>pp[i].first>>pp[i].second;
    
      for(int i=0;i    long long dx=pp[i].first-pp[j].first;
    long long dy=pp[i].second-pp[j].second;
    edg.push_back(make_pair(sqrt(dx*dx+dy*dy+0.0),make_pair(i,j)));
      }
      cin>>n;
      for(int i=0;i
    int u,v;cin>>u>>v;
    Union(u-1,v-1);
      }
     
      sort(edg.begin(),edg.end(),comp);
      double sum=0;
      for(int i=0;i
    int u,v;
    d=edg[i].first;
    u=edg[i].second.first;
    v=edg[i].second.second;
    if(find_set(u)!=find_set(v)){
     Union(u,v);
     sum+=d;
    }
      }
      printf("%.2lf\n",sum);
  }
}