Advertisement
Guest User

CH12 Stargate

a guest
Jun 20th, 2011
1,553
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.61 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.LinkedList;
  5. import java.util.List;
  6. import java.util.StringTokenizer;
  7.  
  8. /*
  9.  * Tuenti Contest
  10.  * Challenge 12 - Stargate
  11.  * Author: Pedro Antonio Pardal Jimena
  12.  */
  13.  
  14. public class Stargate
  15. {
  16.     private static int bellmanFord( int tamano, List<Arco> arcos, int inicio, int fin )
  17.     {      
  18.         Nodo[] nodos = new Nodo[tamano];
  19.        
  20.         /* Inicializar el grafo */
  21.         for ( int i = 0; i < tamano; i++ )
  22.         {
  23.             nodos[i] = new Nodo();
  24.         }
  25.         nodos[inicio].setDistancia( 0 );
  26.        
  27.         /* Relajación de los arcos */
  28.         for ( int i = 0; i < tamano - 1; i++ )
  29.         {
  30.             for ( Arco arco : arcos )  
  31.             {
  32.                 int u = arco.getDesde();
  33.                 int v = arco.getHasta();
  34.                
  35.                 if ( nodos[u].getDistancia() != Integer.MAX_VALUE )
  36.                 {
  37.                     if ( nodos[u].getDistancia() + arco.getPeso() < nodos[v].getDistancia() )
  38.                     {
  39.                         nodos[v].setDistancia( nodos[u].getDistancia() + arco.getPeso() );
  40.                         nodos[v].setPredecesor( u );
  41.                     }
  42.                 }
  43.             }
  44.         }
  45.        
  46.         /* Comprobación de ciclos con coste negativo */
  47.         for ( Arco arco : arcos )  
  48.         {
  49.             int u = arco.getDesde();
  50.             int v = arco.getHasta();
  51.            
  52.             if ( nodos[u].getDistancia() != Integer.MAX_VALUE )
  53.             {
  54.                 if ( nodos[u].getDistancia() + arco.getPeso() < nodos[v].getDistancia() )
  55.                     return Integer.MIN_VALUE;
  56.             }
  57.         }
  58.        
  59.         return nodos[fin].getDistancia();
  60.     }
  61.    
  62.     private static Arco parseArco( String s )
  63.     {
  64.         StringTokenizer st = new StringTokenizer( s, "," );
  65.        
  66.         int desde = Integer.parseInt( st.nextToken() );
  67.         int hasta = Integer.parseInt( st.nextToken() );
  68.         int peso = Integer.parseInt( st.nextToken() );
  69.        
  70.         return new Arco( desde, hasta, peso );
  71.     }
  72.    
  73.     private static final int STARTING_STARDATE = 25000;
  74.    
  75.     public static void main( String[] args )
  76.     {
  77.         BufferedReader reader = new BufferedReader( new InputStreamReader( System.in ) );
  78.    
  79.         try
  80.         {
  81.             while ( reader.ready() )
  82.             {
  83.                 String linea = reader.readLine();
  84.                
  85.                 StringTokenizer st = new StringTokenizer( linea );
  86.                
  87.                 int numberOfPlanets = Integer.parseInt( st.nextToken() );
  88.                 int earthIndex = Integer.parseInt( st.nextToken() );
  89.                 int atlantisIndex = Integer.parseInt( st.nextToken() );
  90.                
  91.                 List<Arco> arcos = new LinkedList<Arco>();
  92.                
  93.                 while ( st.hasMoreTokens() )
  94.                 {
  95.                     arcos.add( parseArco( st.nextToken() ) );
  96.                 }
  97.                
  98.                 int coste = bellmanFord( numberOfPlanets, arcos, earthIndex, atlantisIndex );
  99.                
  100.                 if ( coste == Integer.MIN_VALUE )
  101.                     System.out.println( "BAZINGA" );
  102.                 else
  103.                     System.out.println( STARTING_STARDATE + coste );
  104.             }
  105.         }
  106.         catch ( IOException e )
  107.         {
  108.             System.err.println( "Formato de la entrada incorrecto" );
  109.         }
  110.     }  
  111. }
  112.  
  113.  
  114. ///////////////////////
  115.  
  116.  
  117. public class Nodo
  118. {
  119.     private int _distancia;
  120.     private int _predecesor;
  121.    
  122.     public Nodo()
  123.     {
  124.         _distancia = Integer.MAX_VALUE;
  125.         _predecesor = -1;
  126.     }
  127.    
  128.     public int getDistancia()
  129.     {
  130.         return _distancia;
  131.     }
  132.    
  133.     public void setDistancia( int distancia )
  134.     {
  135.         _distancia = distancia;
  136.     }
  137.    
  138.     public int getPredecesor()
  139.     {
  140.         return _predecesor;
  141.     }
  142.    
  143.     public void setPredecesor( int predecesor )
  144.     {
  145.         _predecesor = predecesor;
  146.     }
  147. }
  148.  
  149. ////////////////////
  150.  
  151.  
  152. public class Arco
  153. {
  154.     private int _desde;
  155.     private int _hasta;
  156.     private int _peso;
  157.    
  158.     public Arco( int desde, int hasta, int peso )
  159.     {
  160.         _desde = desde;
  161.         _hasta = hasta;
  162.         _peso = peso;
  163.     }
  164.    
  165.     public int getDesde()
  166.     {
  167.         return _desde;
  168.     }
  169.    
  170.     public int getHasta()
  171.     {
  172.         return _hasta;
  173.     }
  174.    
  175.     public int getPeso()
  176.     {
  177.         return _peso;
  178.     }
  179. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement