# Shortest Path algo - Java soln

• ``````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;
}

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;