[Java] DijkstraSP using IndexMinPQ with time complexity O(ElogV)
If you use a built-in PriorityQueue to implements dijkstra shortest path algorithm, the time complexity will be O(ElogE), since you may add several edges with d
If you use a built-in PriorityQueue to implements dijkstra shortest path algorithm, the time complexity will be O(ElogE), since you may add several edges with different distances.  By using the indexMinPQ, you could avoid the duplicates and get a O(ElogV). The runtime also improves from [31ms](https://leetcode.com/problems/network-delay-time/discuss/210698/Java-Djikstrabfs-Concise-and-very-easy-to-understandp://)(test from the most voted dijkstra solution) to 8ms.\n\n```\nclass Solution {\n    public int networkDelayTime(int[][] times, int n, int k) {\n        List<Pair<Integer, Integer>>[] g = new List[n];\n        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();\n        for (int[] edge : times) {\n            g[edge[0] - 1].add(new Pair(edge[1] - 1, edge[2]));\n        }\n        IndexMinPQ<Integer> pq = new IndexMinPQ(n);\n        pq.insert(k - 1, 0);\n        int[] distTo = new int[n];\n        Arrays.fill(distTo, Integer.MAX_VALUE);\n        distTo[k - 1] = 0;\n        while (!pq.isEmpty()) {\n            int idx = pq.delMin();\n            int dist = distTo[idx];\n            for (Pair<Integer, Integer> next : g[idx]) {\n                int nidx = next.getKey();\n                int ndist = next.getValue() + dist;\n                if (ndist< distTo[nidx]) {\n                    distTo[nidx] = ndist;\n                    if (!pq.contains(nidx)) pq.insert(nidx, ndist);\n                    else pq.decreaseKey(nidx, ndist);\n                }\n            }\n        }\n        int ans = 0;\n        for (int dist : distTo) ans = Math.max(ans, dist);\n        return ans == Integer.MAX_VALUE ? -1 : ans;\n    }\n}\n\nclass IndexMinPQ<Key extends Comparable<Key>> {\n    private int maxN;        // maximum number of elements on PQ\n    private int n;           // number of elements on PQ\n    private int[] pq;        // binary heap using 1-based indexing\n    private int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = i\n    private Key[] keys;      // keys[i] = priority of i\n\n    public IndexMinPQ(int maxN) {\n        if (maxN < 0) throw new IllegalArgumentException();\n        this.maxN = maxN;\n        n = 0;\n        keys = (Key[]) new Comparable[maxN + 1];\n        pq   = new int[maxN + 1];\n        qp   = new int[maxN + 1];                   \n        for (int i = 0; i <= maxN; i++)\n            qp[i] = -1;\n    }\n    \n    public boolean isEmpty() {\n        return n == 0;\n    }\n\n    public boolean contains(int i) {\n        return qp[i] != -1;\n    }\n\n    public int size() {\n        return n;\n    }\n\n    public void insert(int i, Key key) {\n        n++;\n        qp[i] = n;\n        pq[n] = i;\n        keys[i] = key;\n        swim(n);\n    }    \n    \n    public int minIndex() {\n        return pq[1];\n    }\n\n    public Key minKey() {\n        return keys[pq[1]];\n    }\n\n    public int delMin() {\n        int min = pq[1];\n        exch(1, n--);\n        sink(1);\n        assert min == pq[n+1];\n        qp[min] = -1;        // delete\n        keys[min] = null;    // to help with garbage collection\n        pq[n+1] = -1;        // not needed\n        return min;\n    }\n    \n    public void decreaseKey(int i, Key key) {\n        keys[i] = key;\n        swim(qp[i]);\n    }\n    \n    private boolean greater(int i, int j) {\n        return keys[pq[i]].compareTo(keys[pq[j]]) > 0;\n    }\n\n    private void exch(int i, int j) {\n        int swap = pq[i];\n        pq[i] = pq[j];\n        pq[j] = swap;\n        qp[pq[i]] = i;\n        qp[pq[j]] = j;\n    }\n\n    private void swim(int k) {\n        while (k > 1 && greater(k/2, k)) {\n            exch(k, k/2);\n            k = k/2;\n        }\n    }\n\n    private void sink(int k) {\n        while (2*k <= n) {\n            int j = 2*k;\n            if (j < n && greater(j, j+1)) j++;\n            if (!greater(k, j)) break;\n            exch(k, j);\n            k = j;\n        }\n    }\n}\n```
[]