daily pastebin goal
60%
SHARE
TWEET

CH12 Stargate

a guest Jun 20th, 2011 716 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top