Advertisement
Guest User

CH12 Stargate

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