# The Stargate Problem Java Tuenti Contest

Jun 21st, 2011
1,248
0
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.
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.
124.
125.         try {
126.
128.
130.                 new Stargate(linea);
131.
132.             }
133.
134.         } catch (Exception e) {
135.             e.printStackTrace();
136.         }
137.
138.     }
139.
140. }