Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.FileReader;
- import java.util.Arrays;
- /**
- * Compacts the node data into a dense representation
- *
- * Nodes representation:
- *
- * int rowlength
- *
- * dest | cost | 0 0 0 0 0 ... 0 0
- * dest | cost | x x x x x ... 0 0
- *
- * Testing for zero is marginally faster, exploit this instead of checking against array position against rowlength
- *
- *
- */
- public class jv_dense{
- static int numNodes;
- static int rowlength;
- static final int[] nodes;
- static final boolean[] visited;
- static {
- nodes = readPlaces();
- visited = new boolean[numNodes];
- }
- public static void main(final String[] args) throws Exception{
- final long start = System.currentTimeMillis();
- final int len = getLongestPath(0);
- final long duration = System.currentTimeMillis() - start;
- System.out.printf("%d LANGUAGE Java %d\n", len, duration);
- }
- static int[] readPlaces() {
- try (BufferedReader in = new BufferedReader(new FileReader("agraph"))) {
- final String s = in.readLine();
- numNodes = Integer.parseInt(s);
- final int[][] nodes = new int[numNodes][];
- for(int i = 0; i < numNodes; i++){
- nodes[i]= new int[0];
- }
- rowlength = 0;
- while (in.ready()) {
- final String ln = in.readLine();
- final String[] nums = ln.split("[ \t]+");
- if(nums.length != 3){
- break;
- }
- final int node = Integer.parseInt(nums[0]);
- final int neighbour = Integer.parseInt(nums[1]);
- final int cost = Integer.parseInt(nums[2]);
- final int index = nodes[node].length;
- final int[] replacement = Arrays.copyOf(nodes[node], index + 2);
- replacement[index] = neighbour;
- replacement[index+1] = cost;
- nodes[node] = replacement;
- rowlength = Math.max(rowlength, index + 2);
- }
- // convert nodes to dense format
- rowlength += 2;
- int[] densenodes = new int[numNodes * rowlength];
- for (int i = 0; i < nodes.length; i++) {
- for (int j = 0; j < nodes[i].length; j++) {
- densenodes[i * rowlength + j] = nodes[i][j];
- }
- }
- return densenodes;
- } catch (Exception e) {
- return null;
- }
- }
- static int getLongestPath(final int nodeID){
- visited[nodeID] = true;
- int max=0;
- final int offset = rowlength * nodeID;
- int cost;
- for (int i = 0; (cost = nodes[offset + i + 1]) != 0; i+=2) {
- final int dest = nodes[offset + i];
- if (!visited[dest]) {
- final int dist = cost + getLongestPath(dest);
- if (dist > max) {
- max = dist;
- }
- }
- }
- visited[nodeID] = false;
- return max;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement