HackerEarth Dangerous Dungeon problem solution

In this HackerEarth Dangerous Dungeon problem solution David is playing a video game set in a dungeon. The dungeon has n interesting points and m one way tunnels connecting those points. The i-th tunnel starts at point ai and ends at point bi and takes ci units of time to traverse. Note that it may be possible that there are two tunnels connecting the same pair of points, and even more strangely, a tunnel that goes back to the same point.

David is currently at the point labeled 0, and wishes to travel to the point n-1 using the smallest amount of time.

David discovered that some points become dangerous at some moments of time. More specifically, for each point, David found an integer oi such that point i is dangerous at all times t satisfying t = oi modulo p. The integer p is the same for every single intersection.

David needs to always be in constant motion, and can’t wait at a point. Additionally, he will always be safe in a tunnel, but cannot arrive at a point at the moment it becomes dangerous.

Help David determine the fastest time he can reach his destination.

import java.io.*;
import java.util.*;

public class DangerousCity {
  private static InputReader in;
  private static PrintWriter out;
  
  public static long INF = 1l << 60;
  
  public static void main (String[] args) {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out, true);
    int n = in.nextInt(), m = in.nextInt(), p = in.nextInt();
    
    int[] off = new int[n];
    for (int i = 0; i < n; i++) off[i] = in.nextInt();
    
    ArrayList<Edge>[] fg = new ArrayList[n];
    ArrayList<Edge>[] bg = new ArrayList[n];
    for (int i = 0; i < n; i++) {
      fg[i] = new ArrayList<>();
      bg[i] = new ArrayList<>();
    }
    
    for (int i = 0; i < m; i++) {
      int a = in.nextInt(), b = in.nextInt(), c = in.nextInt();
      fg[a].add(new Edge(b, c));
      bg[b].add(new Edge(a, c));
    }
    
    // find shortest distance from every node to end.
    long[] bdist = new long[n];
    Arrays.fill(bdist, 1l << 60);
    PriorityQueue<Edge> pq = new PriorityQueue<>();
    bdist[n-1] = 0;
    pq.add(new Edge(n-1, 0));
    while (pq.size() > 0) {
      Edge e = pq.poll();
      if (bdist[e.to] != e.weight) continue;
      for (Edge next : bg[e.to]) {
        long nn = next.weight + e.weight;
        if (nn < bdist[next.to]) {
          pq.add(new Edge(next.to, bdist[next.to] = nn));
        }
      }
    }
    
    // A* search
    HashMap<Long, Long>[] smods = new HashMap[n];
    for (int i = 0; i < n; i++) smods[i] = new HashMap<>();
    
    long ans = INF;
    if (off[0] != 0) {
      smods[0].put(0l, 0l);
      pq.add(new Edge(0, 0 + bdist[0]));
    }
    while (pq.size() > 0) {
      Edge e = pq.poll();
      long aw = e.weight - bdist[e.to];
      Long x = smods[e.to].get(aw % p);
      if (x == null || x != aw) continue;
      if (e.to == n-1) {
        ans = aw;
        break;
      }
      for (Edge next : fg[e.to]) {
        long nn = next.weight + aw;
        Long y = smods[next.to].get(nn % p);
        if (nn % p != off[next.to] && (y == null || nn < y)) {
          smods[next.to].put(nn % p, nn);
          pq.add(new Edge(next.to, nn + bdist[next.to]));
        }
      }
    }
    
    out.println(ans >= INF ? -1 : ans);
    out.close();
    System.exit(0);
  }
  
  static class Edge implements Comparable<Edge> {
    public int to;
    public long weight;
    public Edge (int to, long weight) {
      this.to = to;
      this.weight = weight;
    }
    public int compareTo(Edge other) {
      return Long.compare(weight, other.weight);
    }
  }
  
  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }
}