daily pastebin goal
22%
SHARE
TWEET

StargateProblem

alefhidalgo Jun 20th, 2011 708 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Scanner;
  4.  
  5.  
  6. /**
  7.  * Tuenti Programming Contest
  8.  * Challenge 12: The Stargate Problem
  9.  * @author alefhidalgo [at] gmail [dot] com
  10.  */
  11. public class StargateProblem {
  12.        
  13.         public static final int BASE_TIME = 25000; /* Base Time */
  14.         public static final String BAZINGA = "BAZINGA";
  15.         public static final long INFINITY = 999999999999999999L;
  16.        
  17.         /** Edge Class */
  18.         private static class Edge {
  19.                 int source;
  20.                 int dest;
  21.                 int weight;
  22.                 public Edge(int source,int dest, int weigth){
  23.                         this.source = source;
  24.                         this.dest = dest;
  25.                         this.weight = weigth;                  
  26.                 }
  27.         }
  28.         /**
  29.          * Modified Bellman - Ford Algorithm
  30.          * @param edges
  31.          * @param nodecount
  32.          * @param source
  33.          * @param destiny
  34.          */
  35.         public static void doBellmanFord(List<Edge> edges, int nodecount, int earthIndex, int atlantisIndex) {         
  36.            long []distance = new long[nodecount];
  37.            int edgecount = edges.size();
  38.            for (int i=0; i < nodecount; i++) {
  39.              distance[i] = INFINITY;
  40.            }     
  41.            distance[earthIndex] = 0;     
  42.            for (int i=0; i < nodecount; i++) {
  43.                for (int j=0; j < edgecount; j++) {
  44.                    if (distance[edges.get(j).source] != INFINITY) {
  45.                            long new_distance = distance[edges.get(j).source] + edges.get(j).weight;
  46.                        if (new_distance < distance[edges.get(j).dest])
  47.                          distance[edges.get(j).dest] = new_distance;
  48.                    }
  49.                }
  50.            }
  51.            for (int i=0; i < edgecount; i++) {
  52.                if (distance[edges.get(i).dest] > distance[edges.get(i).source] + edges.get(i).weight) {
  53.                    System.out.println("BAZINGA");  
  54.                    return;
  55.                }
  56.            }
  57.            System.out.println(distance[atlantisIndex] == StargateProblem.INFINITY ? BAZINGA : (distance[atlantisIndex] + BASE_TIME));
  58.         }
  59.  
  60.  
  61.         public static void main(String args[]){  
  62.            List<Edge> edges = null;
  63.            Scanner in = new Scanner(System.in);
  64.            Scanner lineScanner = null;
  65.            Scanner plannetScanner = null;
  66.            int nPlanets = 0;
  67.            int earthIndex = 0;
  68.            int atlantisIndex = 0;
  69.            while(in.hasNextLine()){
  70.                    lineScanner = new Scanner(in.nextLine());
  71.                    nPlanets = lineScanner.nextInt();
  72.                    earthIndex = lineScanner.nextInt();
  73.                    atlantisIndex = lineScanner.nextInt();
  74.                    edges = new ArrayList<Edge>();
  75.                    while(lineScanner.hasNext()){
  76.                            plannetScanner = new Scanner(lineScanner.next());
  77.                            plannetScanner.useDelimiter(",");
  78.                            edges.add(new Edge(plannetScanner.nextInt(),plannetScanner.nextInt(),plannetScanner.nextInt()));                                
  79.                    }           
  80.                    doBellmanFord(edges, nPlanets+1, earthIndex, atlantisIndex);
  81.            }
  82.                
  83.         }
  84. }
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