alefhidalgo

StargateProblem

Jun 20th, 2011
898
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