Skip to content

Instantly share code, notes, and snippets.

@Medeah
Created March 28, 2015 09:29
Show Gist options
  • Save Medeah/e401674b2067363265cc to your computer and use it in GitHub Desktop.
Save Medeah/e401674b2067363265cc to your computer and use it in GitHub Desktop.
Accenture challenge using algorithm implementation from here: http://algs4.cs.princeton.edu/code/
import java.io.IOException;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.List;
public class Main {
private static int getNode(int i, int j) {
return i * 1000 + j;
}
public static void main(String[] args) {
EdgeWeightedDigraph test = new EdgeWeightedDigraph(1000 * 1000);
int first = 0;
try {
List<String> lines = Files.readAllLines(Paths.get("ShortestPathProblem.txt"), Charset.defaultCharset());
for (int i = 0; i < lines.size(); i++) {
String line = lines.get(i);
String elms[] = line.split(";");
if (i == 0) {
first = Integer.parseInt(elms[0]);
}
for (int j = 0; j < elms.length; j++) {
int weight = Integer.parseInt(elms[j]);
if (i != 0) {
test.addEdge(new DirectedEdge(getNode(i - 1, j), getNode(i, j), weight));
}
if (i != 999) {
test.addEdge(new DirectedEdge(getNode(i + 1, j), getNode(i, j), weight));
}
if (j != 0) {
test.addEdge(new DirectedEdge(getNode(i, j - 1), getNode(i, j), weight));
}
if (j != 999) {
test.addEdge(new DirectedEdge(getNode(i, j + 1), getNode(i, j), weight));
}
}
}
System.out.println("done adding edges");
} catch (IOException e) {
e.printStackTrace();
}
DijkstraSP path = new DijkstraSP(test, 0);
System.out.println(path.distTo(1000 * 1000 - 1) + first);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment