Shortest Path algo - Java soln


  • 0
    V
    class Node {
        int pre;
        int index;
        int sum;
        public Node(int p, int i, int s) {
            pre = p;
            index = i;
            sum = s;
        }
    }
    
    public class Solution {
        PriorityQueue<Node> pq;
        int[] coins;
        int[] pre;
        public List<Integer> cheapestJump(int[] A, int B) {
            List<Integer> list = new ArrayList<>();
            if(A == null || A.length == 0 || B < 1) return list;
            int len = A.length;
            pq= new PriorityQueue<>((a, b) -> a.sum == b.sum? a.index - b.index : a.sum - b.sum);
            coins = new int[len];
            pre = new int[len];
            for(int i=0; i<len; i++) {
                coins[i] = Integer.MAX_VALUE;
            }
            
            pq.add(new Node(0, 0, A[0]));
            
            while(!pq.isEmpty()) {
                Node n = pq.poll();
                if(n.index == len-1) {
                    pre[n.index] = n.pre;
                    coins[n.index] = n.sum;
                    break;
                }
                if(n.sum < coins[n.index]) {
                    pre[n.index] = n.pre;
                    coins[n.index] = n.sum;
                }
                
                for(int i=1; i<=B; i++) {
                    int cur = n.index;
                    int next = n.index+i;
                    if(next < len && A[next] != -1) pq.add(new Node(cur, next, coins[cur]+A[next]));
                }
            }
            
            if(coins[len-1] != Integer.MAX_VALUE) {
                //traverse pre from len-1 to 0 and add to list
                int j = len-1;
                list.add(j+1);
                while(j != pre[j]) {
                    list.add(pre[j]+1);
                    j = pre[j];
                }
                Collections.reverse(list);
            }
            return list;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.