Advertisement
super_tycoon

lpath crappy java

Dec 20th, 2014
228
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.55 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.FileReader;
  3. import java.util.Arrays;
  4.  
  5. /**
  6.  * Compacts the node data into a dense representation
  7.  *
  8.  * Nodes representation:
  9.  *
  10.  * int rowlength
  11.  *
  12.  * dest | cost | 0 0 0 0 0 ... 0 0
  13.  * dest | cost | x x x x x ... 0 0
  14.  *
  15.  * Testing for zero is marginally faster, exploit this instead of checking against array position against rowlength
  16.  *
  17.  *
  18.  */
  19. public class jv_dense{
  20.  
  21.     static int numNodes;
  22.     static int rowlength;
  23.     static final int[] nodes;
  24.     static final boolean[] visited;
  25.  
  26.     static {
  27.         nodes = readPlaces();
  28.         visited = new boolean[numNodes];
  29.     }
  30.  
  31.     public static void main(final String[] args) throws Exception{
  32.         final long start = System.currentTimeMillis();
  33.         final int len = getLongestPath(0);
  34.         final long duration = System.currentTimeMillis() - start;
  35.         System.out.printf("%d LANGUAGE Java %d\n", len, duration);
  36.     }
  37.  
  38.     static int[] readPlaces() {
  39.         try (BufferedReader in = new BufferedReader(new FileReader("agraph"))) {
  40.             final String s = in.readLine();
  41.             numNodes = Integer.parseInt(s);
  42.             final int[][] nodes = new int[numNodes][];
  43.             for(int i = 0; i < numNodes; i++){
  44.                 nodes[i]= new int[0];
  45.             }
  46.  
  47.             rowlength = 0;
  48.  
  49.             while (in.ready()) {
  50.                 final String ln = in.readLine();
  51.                 final String[] nums = ln.split("[ \t]+");
  52.                 if(nums.length != 3){
  53.                     break;
  54.                 }
  55.                 final int node = Integer.parseInt(nums[0]);
  56.                 final int neighbour = Integer.parseInt(nums[1]);
  57.                 final int cost = Integer.parseInt(nums[2]);
  58.  
  59.                 final int index = nodes[node].length;
  60.                 final int[] replacement = Arrays.copyOf(nodes[node], index + 2);
  61.                 replacement[index] = neighbour;
  62.                 replacement[index+1] = cost;
  63.  
  64.                 nodes[node] = replacement;
  65.  
  66.                 rowlength = Math.max(rowlength, index + 2);
  67.             }
  68.  
  69.             // convert nodes to dense format
  70.  
  71.             rowlength += 2;
  72.  
  73.             int[] densenodes = new int[numNodes * rowlength];
  74.  
  75.             for (int i = 0; i < nodes.length; i++) {
  76.                 for (int j = 0; j < nodes[i].length; j++) {
  77.                     densenodes[i * rowlength + j] = nodes[i][j];
  78.                 }
  79.             }
  80.  
  81.             return densenodes;
  82.         } catch (Exception e) {
  83.             return null;
  84.         }
  85.     }
  86.  
  87.     static int getLongestPath(final int nodeID){
  88.         visited[nodeID] = true;
  89.         int max=0;
  90.  
  91.         final int offset = rowlength * nodeID;
  92.  
  93.         int cost;
  94.         for (int i = 0; (cost = nodes[offset + i + 1]) != 0; i+=2) {
  95.  
  96.             final int dest = nodes[offset + i];
  97.  
  98.             if (!visited[dest]) {
  99.                 final int dist = cost + getLongestPath(dest);
  100.                 if (dist > max) {
  101.                     max = dist;
  102.                 }
  103.             }
  104.         }
  105.  
  106.         visited[nodeID] = false;
  107.         return max;
  108.     }
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement