# UVA 1112 – Mice and Maze

This question is part of the Competitive Programming 3 book however I haven’t quite reached that chapter yet. Let me see how my approach to solving this problem changes once I get there.

Below is the way I would have done it without having reading the book.

```import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
*
* @author Sanchit M. Bhatnagar
* @see http://uhunt.felix-halim.net/id/74004
*
*/
public class P1112 {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);

int zz = sc.nextInt();
for (int i = 0; i &lt; zz; i++) {
if (i != 0)
out.println();
int N = sc.nextInt();
int E = sc.nextInt() - 1;
int T = sc.nextInt();
int M = sc.nextInt();
Node[] graph = new Node[N];
for (int j = 0; j &lt; N; j++) {
graph[j] = new Node(j);
}
for (int j = 0; j &lt; M; j++) {
int a = sc.nextInt() - 1;
int b = sc.nextInt() - 1;
int c = sc.nextInt();
}
int[] shortest = new int[N];
for (int j = 0; j &lt; N; j++) {
if (shortest[j] == 0) {
Object[] output = dfs(graph, j, E);
if (output != null) {
@SuppressWarnings(&quot;unchecked&quot;)
ArrayList&lt;Integer&gt; tmp = (ArrayList&lt;Integer&gt;) output[0];
int cost = (int) output[1];
int size = tmp.size();
int thing = 0;
shortest[tmp.get(0)] = cost;
for (int k = 1; k &lt; size; k++) {
thing += graph[tmp.get(k - 1)].cost.get(tmp.get(k));
shortest[tmp.get(k)] = cost - thing;
}
} else {
shortest[j] = -1;
}
for (int k = 0; k &lt; N; k++) {
graph[k].visited = false;
}
}
}
int ans = 0;
for (int j = 0; j &lt; N; j++) {
if (shortest[j] &lt;= T &amp;&amp; shortest[j] != -1) {
ans++;
}
}
out.println(ans);
}
out.close();
sc.close();
}

@SuppressWarnings(&quot;unchecked&quot;)
private static Object[] dfs(Node[] graph, int j, int e) {
PriorityQueue&lt;Object[]&gt; queue = new PriorityQueue&lt;Object[]&gt;(1, new Comparator&lt;Object[]&gt;() {
@Override
public int compare(Object[] o1, Object[] o2) {
return Integer.compare((int) o1[2], (int) o2[2]);
}
});
queue.add(new Object[] { graph[j], new ArrayList&lt;Integer&gt;(), 0 });
while (!queue.isEmpty()) {
Object[] next = queue.poll();
Node n = ((Node) next[0]);
n.visited = true;
if (n.idx == e) {
return new Object[] { next[1], next[2] };
} else {
for (Integer in : n.cost.keySet()) {
if (!graph[in].visited) {
ArrayList&lt;Integer&gt; tmp = new ArrayList&lt;Integer&gt;();
queue.add(new Object[] { graph[in], tmp, (int) next[2] + n.cost.get(in) });
}
}
}
}
return null;
}

private static class Node {
boolean visited;
int idx;
HashMap&lt;Integer, Integer&gt; cost;

public Node(int idx) {
this.idx = idx;
cost = new HashMap&lt;Integer, Integer&gt;();
}

public void add(Node n, int cost) {
if (this.cost.containsKey(n.idx)) {
int tmp = this.cost.get(n);
this.cost.put(n.idx, Math.min(tmp, cost));
} else {
this.cost.put(n.idx, cost);
}
}
}

}
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.