UVa Online Judge Challenge "1112"
This problem involves a relatively small graph, so I opted to implement the Floyd-Warshall Algorithm instead of Dijkstra's Algorithm for the sake of simplicity. This algorithm finds the shortest path between every pair of vertices in a graph, running in O(n^3) time. Although this might sound inefficient, the UVA judge accepted this program with a runtime of 0.12 seconds, which is well within the 3-second threshold. I designed this algorithm using an object-oriented approach and avoided arrays, so that if I ever have enough free time, I can easily integrate it into Processing and visualize it in 3D.
Problem
My Solution
1import java.io.BufferedReader;
2import java.io.IOException;
3import java.io.InputStreamReader;
4import java.util.ArrayList;
5public class Main {
6 static int N;
7 public static void main(String[] args) throws IOException {
8 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
9 final int MAX = 101;
10 int cases, E, T, M;
11 String blank;
12 cases = Integer.parseInt(br.readLine());
13 while (cases-- > 0) {
14 ArrayList<myPoint3D> cells = new ArrayList();
15 blank = br.readLine();
16 N = Integer.parseInt(br.readLine());
17 E = Integer.parseInt(br.readLine());
18 T = Integer.parseInt(br.readLine());
19 M = Integer.parseInt(br.readLine());
20 /*
21 1. let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
22 2. for each edge (u,v)
23 3. dist[u][v] ← w(u,v) // the weight of the edge (u,v)
24 */
25 for (int x = 0; x < N; x++) {
26 for (int y = 0; y < N; y++) {
27 cells.add(new myPoint3D(x, y, MAX));
28 }
29 }
30 /*
31 4. for each vertex v
32 5. dist[v][v] ← 0
33 --------------------------------------------------------------------
34 The time it takes to get from any vertex to itself is always going to be zero.
35 */
36 for (int i = 0; i < N; i++) {
37 int index = getIndex(i, i);
38 cells.get(index).z = 0;
39 }
40 /*
41 Modify the grid with the UVA problem inputs
42 */
43 for (int i = 0; i < M; i++) {
44 String[] temp = br.readLine().split(" ");
45 int a = Integer.parseInt(temp[0]) - 1;
46 int b = Integer.parseInt(temp[1]) - 1;
47 int t = Integer.parseInt(temp[2]);
48 int index = getIndex(a, b);
49 cells.get(index).z = t;
50 }
51 /*
52 6. for k from 1 to |V|
53 7. for i from 1 to |V|
54 8. for j from 1 to |V|
55 9. if dist[i][j] > dist[i][k] + dist[k][j]
56 10. dist[i][j] ← dist[i][k] + dist[k][j]
57 11. end if
58 */
59 for (int k = 0; k < N; k++) {
60 for (int i = 0; i < N; i++) {
61 for (int j = 0; j < N; j++) {
62 int IJ = getIndex(i, j);
63 int IK = getIndex(i, k);
64 int KJ = getIndex(k, j);
65 if (cells.get(IJ).z > cells.get(IK).z + cells.get(KJ).z) {
66 cells.get(IJ).z = cells.get(IK).z + cells.get(KJ).z;
67 }
68 }
69 }
70 }
71 int counter = 0;
72 for (int i = 0; i < N; i++) {
73 int index = getIndex(i, E - 1);
74 if (cells.get(index).z <= T) {
75 counter++;
76 }
77 }
78 System.out.println(counter);
79 if (cases > 0) {
80 System.out.println("");
81 }
82 }
83 }
84 static int getIndex(int x, int y) {
85 return x * N + y;
86 }
87}
88class myPoint3D {
89 int x;
90 int y;
91 int z;
92 myPoint3D(int x, int y, int z) {
93 this.x = x;
94 this.y = y;
95 this.z = z;
96 }
97}