SHARE
TWEET

The Stargate Problem Java Tuenti Contest

javipinero Jun 21st, 2011 710 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
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