CH12 Stargate

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: [email protected]
 */

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;
    }
}