Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.LinkedList;
- import java.util.List;
- import java.util.StringTokenizer;
- /*
- * Tuenti Contest
- * Challenge 12 - Stargate
- * Author: Pedro Antonio Pardal Jimena
- * Email: pardal@alu.uma.es
- */
- public class Stargate
- {
- private static int bellmanFord( int tamano, List<Arco> arcos, int inicio, int fin )
- {
- Nodo[] nodos = new Nodo[tamano];
- /* Inicializar el grafo */
- for ( int i = 0; i < tamano; i++ )
- {
- nodos[i] = new Nodo();
- }
- nodos[inicio].setDistancia( 0 );
- /* Relajación de los arcos */
- for ( int i = 0; i < tamano - 1; i++ )
- {
- for ( Arco arco : arcos )
- {
- int u = arco.getDesde();
- int v = arco.getHasta();
- if ( nodos[u].getDistancia() != Integer.MAX_VALUE )
- {
- if ( nodos[u].getDistancia() + arco.getPeso() < nodos[v].getDistancia() )
- {
- nodos[v].setDistancia( nodos[u].getDistancia() + arco.getPeso() );
- nodos[v].setPredecesor( u );
- }
- }
- }
- }
- /* Comprobación de ciclos con coste negativo */
- for ( Arco arco : arcos )
- {
- int u = arco.getDesde();
- int v = arco.getHasta();
- if ( nodos[u].getDistancia() != Integer.MAX_VALUE )
- {
- if ( nodos[u].getDistancia() + arco.getPeso() < nodos[v].getDistancia() )
- return Integer.MIN_VALUE;
- }
- }
- return nodos[fin].getDistancia();
- }
- private static Arco parseArco( String s )
- {
- StringTokenizer st = new StringTokenizer( s, "," );
- int desde = Integer.parseInt( st.nextToken() );
- int hasta = Integer.parseInt( st.nextToken() );
- int peso = Integer.parseInt( st.nextToken() );
- return new Arco( desde, hasta, peso );
- }
- private static final int STARTING_STARDATE = 25000;
- public static void main( String[] args )
- {
- BufferedReader reader = new BufferedReader( new InputStreamReader( System.in ) );
- try
- {
- while ( reader.ready() )
- {
- String linea = reader.readLine();
- StringTokenizer st = new StringTokenizer( linea );
- int numberOfPlanets = Integer.parseInt( st.nextToken() );
- int earthIndex = Integer.parseInt( st.nextToken() );
- int atlantisIndex = Integer.parseInt( st.nextToken() );
- List<Arco> arcos = new LinkedList<Arco>();
- while ( st.hasMoreTokens() )
- {
- arcos.add( parseArco( st.nextToken() ) );
- }
- int coste = bellmanFord( numberOfPlanets, arcos, earthIndex, atlantisIndex );
- if ( coste == Integer.MIN_VALUE )
- System.out.println( "BAZINGA" );
- else
- System.out.println( STARTING_STARDATE + coste );
- }
- }
- catch ( IOException e )
- {
- System.err.println( "Formato de la entrada incorrecto" );
- }
- }
- }
- ///////////////////////
- public class Nodo
- {
- private int _distancia;
- private int _predecesor;
- public Nodo()
- {
- _distancia = Integer.MAX_VALUE;
- _predecesor = -1;
- }
- public int getDistancia()
- {
- return _distancia;
- }
- public void setDistancia( int distancia )
- {
- _distancia = distancia;
- }
- public int getPredecesor()
- {
- return _predecesor;
- }
- public void setPredecesor( int predecesor )
- {
- _predecesor = predecesor;
- }
- }
- ////////////////////
- public class Arco
- {
- private int _desde;
- private int _hasta;
- private int _peso;
- public Arco( int desde, int hasta, int peso )
- {
- _desde = desde;
- _hasta = hasta;
- _peso = peso;
- }
- public int getDesde()
- {
- return _desde;
- }
- public int getHasta()
- {
- return _hasta;
- }
- public int getPeso()
- {
- return _peso;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement