javipinero

The Stargate Problem Java Tuenti Contest

Jun 21st, 2011
879
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**************************************
  2.  ** Fichero Arista.java
  3.  *************************************/
  4.  
  5. package stargate;
  6.  
  7. public class Arista {
  8.  
  9.     public int source;
  10.     public int destination;
  11.     public int weight;
  12.    
  13.     public Arista(int source, int destination, int weight) {
  14.         this.source = source;
  15.         this.destination = destination;
  16.         this.weight = weight;
  17.     }
  18. }
  19.  
  20.  
  21. /**************************************
  22.  ** Fichero BellmanFord.java
  23.  *************************************/
  24.  
  25.  
  26. package stargate;
  27.  
  28. public class BellmanFord {
  29.  
  30.     public static int INFINITO = 999999999;
  31.  
  32.     public static int algoritmoBellmanFord(Arista aristas[], int nodos,
  33.             int inicio, int fin) {
  34.  
  35.         int numArista = aristas.length;
  36.         int distancia[] = new int[32];
  37.  
  38.  
  39.         for (int i = 0; i < nodos; ++i) {
  40.             distancia[i] = INFINITO;
  41.         }
  42.  
  43.         distancia[inicio] = 0;
  44.  
  45.         for (int i = 0; i < nodos; ++i) {
  46.            
  47.             for (int j = 0; j < numArista; ++j) {
  48.                
  49.                 if (distancia[aristas[j].source] != INFINITO) {
  50.                    
  51.                     if (distancia[aristas[j].source] + aristas[j].weight < distancia[aristas[j].destination]) {
  52.                        
  53.                         int dummy = distancia[aristas[j].source]
  54.                                 + aristas[j].weight;
  55.                        
  56.                         if (dummy < distancia[aristas[j].destination])
  57.                             distancia[aristas[j].destination] = dummy;
  58.                    
  59.                     }
  60.                
  61.                 }
  62.            
  63.             }
  64.        
  65.         }
  66.  
  67.         for (int i = 0; i < numArista; ++i) {
  68.             if (distancia[aristas[i].destination] > distancia[aristas[i].source]
  69.                     + aristas[i].weight) {
  70.                 return INFINITO;
  71.             }
  72.         }
  73.        
  74.         return distancia[fin];
  75.  
  76.     }
  77. }
  78.  
  79. /**************************************
  80.  ** Fichero Stargate.java
  81.  *************************************/
  82.  
  83. package stargate;
  84.  
  85. import java.io.BufferedReader;
  86. import java.io.InputStreamReader;
  87. import java.util.StringTokenizer;
  88.  
  89. public class Stargate {
  90.  
  91.     int numeroPlanetas;
  92.     int indiceTierra;
  93.     int indiceAtlantis;
  94.    
  95.     public Stargate(String linea) {
  96.         StringTokenizer datos = new StringTokenizer(linea);
  97.         numeroPlanetas = Integer.parseInt(datos.nextToken());
  98.         indiceTierra = Integer.parseInt(datos.nextToken());
  99.         indiceAtlantis = Integer.parseInt(datos.nextToken());
  100.        
  101.         Arista[] edge = new Arista[datos.countTokens()];
  102.         int i = 0;
  103.        
  104.         while (datos.hasMoreTokens()) {
  105.             StringTokenizer datosAux = new StringTokenizer(datos.nextToken(), ",");
  106.             int planetaInicio = Integer.parseInt(datosAux.nextToken());
  107.             int planetaFin = Integer.parseInt(datosAux.nextToken());
  108.             edge[i] = new Arista(planetaInicio, planetaFin, Integer.parseInt(datosAux.nextToken()));
  109.             i++;
  110.         }
  111.        
  112.         int distancia = BellmanFord.algoritmoBellmanFord(edge, numeroPlanetas, indiceTierra, indiceAtlantis);
  113.         if (distancia == BellmanFord.INFINITO) {
  114.             System.out.println("BAZINGA");
  115.         } else {
  116.             System.out.println(25000+distancia);
  117.         }
  118.        
  119.     }
  120.    
  121.     public static void main(String[] args) {
  122.        
  123.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  124.        
  125.         try {
  126.            
  127.             while (br.ready()) {
  128.                
  129.                 String linea = br.readLine();
  130.                 new Stargate(linea);
  131.                
  132.             }
  133.            
  134.         } catch (Exception e) {
  135.             e.printStackTrace();
  136.         }
  137.  
  138.     }
  139.  
  140. }
RAW Paste Data