import java.util.*;
public class LazyDijkstraSP {
private boolean[] marked;
private double[] distTo;
private DirectedEdge[] edgeTo;
private Queue<DirectedEdge> pq;
private class ByDistanceFromSource implements Comparator<DirectedEdge> {
public int compare(DirectedEdge e, DirectedEdge f) {
return Double.compare(distTo[e.from()] + e.weight(), distTo[f.from()] + f.weight());
}
}
public LazyDijkstraSP(EdgeWeightedDigraph G, int s) {
pq = new PriorityQueue<DirectedEdge>(new ByDistanceFromSource());
marked = new boolean[G.V()];
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];
for(int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
relax(G, s);
while(!pq.isEmpty()) {
DirectedEdge e = pq.poll();
int w = e.to();
if(!marked[w]) relax(G, w);
}
}
private void relax(EdgeWeightedDigraph G, int v) {
marked[v] = true;
for(DirectedEdge e : G.adj(v)) {
int w = e.to();
if(distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
pq.offer(e);
}
}
}
public double distTo(int v) {return distTo[v];}
public boolean hasPathTo(int v) {return marked[v];}
public Iterable<DirectedEdge> pathTo(int v) {
if(!hasPathTo(v)) return null;
Stack<DirectedEdge> path = new Stack<>();
for(DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.push(e);
}
return path;
}
}
