Spoj The Shortest Path problem Solution

TheShortestPath.java

package com.problems;
/**
 * @Author Mehdi Maick
 * Created on 18/09/2016.
 */

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

public class TheShortestPath {
    
    static class Edge implements Comparable<Edge> {
        int to, cost;

        public Edge(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return cost - o.cost;
        }
    }
    
    public static int INF = 9999999;
    public static ArrayList<ArrayList<Edge>> g;

    public static void solve(FastReader fs, PrintWriter pw) {
        int t = fs.nextInt();
        HashMap<String, Integer> toI = new HashMap<>();
        while (t-- > 0) {
            int n = fs.nextInt();
            g = new ArrayList<>();
            for (int i = 0; i < n + 2; i++) {
                g.add(new ArrayList<>());
            }
            for (int i = 1; i <= n; i++) {
                String city = fs.next();
                toI.put(city, i);
                int p = fs.nextInt();
                for (int j = 0; j < p; j++) {
                    int a = fs.nextInt();
                    int b = fs.nextInt();
                    g.get(i).add(new Edge(a, b));
                    g.get(a).add(new Edge(i, b));
                }
            }
            
            int q = fs.nextInt();
            for (int i = 0; i < q; i++) {
                String from = fs.next();
                String to = fs.next();
                pw.println(dijekstra(toI.get(from), toI.get(to), n + 1));
            }
            toI.clear();
            
        }
    }

    private static int dijekstra(int from, int to, int V) {
        
        int[] dist = new int[V + 1];
        Arrays.fill(dist, INF);
        dist[from] = 0;
        PriorityQueue<Edge> p = new PriorityQueue<>();
        p.add(new Edge(from, 0));
        while (!p.isEmpty()) {
            int node = p.poll().to;
            if (node == to) {
                return dist[node];
            }
            for (Edge e : g.get(node)) {
                int v = e.to;
                int weight = e.cost;
                if (dist[v] > dist[node] + weight) {
                    dist[v] = dist[node] + weight;
                    p.add(new Edge(v, dist[v]));
                }
            }
        }
        return dist[to];
    }

    public static void main(String[] args) throws Exception {
        FastReader fs = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

        solve(fs, pw);

        fs.close();
        pw.close();
    }

    static class FastReader {

        BufferedReader reader;
        StringTokenizer st;

        FastReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            st = null;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String line = reader.readLine();
                    if (line == null) {
                        return null;
                    }
                    st = new StringTokenizer(line);
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            String s = null;
            try {
                s = reader.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }

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

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        char nextChar() {
            return next().charAt(0);
        }

        int[] nextIntArray(int n) {
            int[] arr = new int[n];
            int i = 0;
            while (i < n) {
                arr[i++] = nextInt();
            }
            return arr;
        }

        long[] nextLongArray(int n) {
            long[] arr = new long[n];
            int i = 0;
            while (i < n) {
                arr[i++] = nextLong();
            }
            return arr;
        }

        int[] nextIntArrayOneBased(int n) {
            int[] arr = new int[n + 1];
            int i = 1;
            while (i <= n) {
                arr[i++] = nextInt();
            }
            return arr;
        }

        long[] nextLongArrayOneBased(int n) {
            long[] arr = new long[n + 1];
            int i = 1;
            while (i <= n) {
                arr[i++] = nextLong();
            }
            return arr;
        }

        void close() {
            try {
                reader.close();
            } catch (IOException e) {
                System.err.println("There's been an error trying closing the reader ");
                e.printStackTrace();
            }
        }
    }


}