Weighted Digraph

import java.util.*;

public class Diagraph {

}

// Directed Graph with first order
class DirectedGraph {
    public int V;
    public int E;
    public ArrayList<Integer>[] adj;

    public DirectedGraph(int V) {
        this.V = V;
        adj = (ArrayList<Integer>[]) new ArrayList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new ArrayList();
        }    
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
        E++;
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];    
    }

    public DirectedGraph reverse() {
        DirectedGraph r = new DirectedGraph(V);
        for (int v = 0; v < V; v++) {
            for (int w : this.adj(v)) {
                r.addEdge(w, v);
            }
        }
        return r;
    }

    public String toString() {
        String s = V + " vertices, " + E + " edges\n";
        for (int v = 0; v < V; v++) {
            s += v + ": ";
            for (int w : this.adj[v]) {
                s += w + " ";
            }
            s += "\n";
        }
        return s;
    }
}

class DirectedCycle {

    public boolean[] marked;
    public int[] edgeTo;
    public Stack<Integer> cycle;
    public boolean[] onStack;

    public DirectedCycle(DirectedGraph G) {
        onStack = new boolean[G.V];
        marked = new boolean[G.V];
        for (int i = 0; i < G.V; i++) {
            if (!marked[i])
                dfs(G, i);
        }
    }

    /**
     * This class adds to our standard recursive 
     * dfs() a boolean array onStack[] to keep track of the 
     * vertices for which the recursive call has not completed. 
     * When it finds an edge v->w to a vertex w that is on the stack, 
     * it has discovered a directed cycle, which it can recover by following edgeTo[] links.
     */
    public void dfs(DirectedGraph G, int v) {
        onStack[v] = true;
        marked[v] = true;
        for (int w : G.adj[v]) {
            if (hasCycle()) {
                return;
            } else if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, w);
            } else if (onStack[w]) {
                cycle = new Stack();
                for(int x = v; x != w; x = edgeTo[w]) {
                    cycle.push(w);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v] = false;
    }

    public boolean hasCycle() {
        return null != cycle;
    }

    public Iterable<Integer> cycle() {
        return cycle;
    }

}


class DepthFirstOrder {

    public boolean[] marked;
    public LinkedList<Integer> pre;
    public LinkedList<Integer> post;
    public Stack<Integer> reversePost;

    public DepthFirstOrder(DirectedGraph G) {
        pre = new LinkedList();
        post = new LinkedList();
        reversePost = new Stack();

        marked = new boolean[G.V];
        for (int i = 0; i < G.V; i++) {
            if (!marked[i])
                dfs(G, i);
        }
    }

    public void dfs(DirectedGraph G, int v) {
        marked[v] = true;
        pre.add(v);
        for (int w : G.adj[v]) {
         if (!marked[w]) {
            dfs(G, w);
         }
        }
        post.add(v);
        reversePost.push(v);
    }
}

class Topological {
    public List<Integer> order;

    public Topological(DirectedGraph G) {
        DirectedCycle cycleFinder = new DirectedCycle(G);
        if (!cycleFinder.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePost;
        }
    }
}


class KosarajuSCC {
    public boolean[] marked;
    public int[] id;
    private int count;

    public KosarajuSCC(DirectedGraph G) {
        marked = new boolean[G.V];
        id = new int[G.V];
        DepthFirstOrder order = new DepthFirstOrder(G.reverse());

        for (int s : order.reversePost) {
            if (!marked[s]) {
                dfs(G, s);
                count++;
            }
        }
    }

    private void dfs(DirectedGraph G, int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj[v]) {
            if (!marked[w])
                dfs(G, w);
        }    
    }

    public boolean stronglyConnected(int w, int v) {
        return id[w] == id[v];
    }

    public int id(int v) {
        return id[v];
    }

}


class DirectedEdge {
   private final int v; //edge source
   private final int w; //edge target
   private final double weight; //edge weight

   public DirectedEdge(int v, int w, double weight){
      this.v = v;
      this.w = w;
      this.weight = weight;
   }

   public double weight()
   {  return weight;  }

   public int from()
   {  return v;  }
   public int to()
   {  return w;  }
   public String toString()
   {  return String.format("%d->%d %.2f", v, w, weight);  }
}


class EdgeWeightedDigraph {
   private final int V; //number of vertices
   private int E; //number of edges
   private ArrayList<DirectedEdge>[] adj; //adjacency lists

   public EdgeWeightedDigraph(int V) {
       this.V = V;
       this.E = 0;
       adj = (ArrayList<DirectedEdge>[]) new ArrayList[V];
       for (int v = 0; v < V; v++)
           adj[v] = new ArrayList<DirectedEdge>();
   }

   public int V() {  return V;  }
   public int E() {  return E;  }

   public void addEdge(DirectedEdge e) {
      adj[e.from()].add(e);
      E++; 
   }

   public Iterable<DirectedEdge> adj(int v)
   {  return adj[v];  }

   public Iterable<DirectedEdge> edges() {
       ArrayList<DirectedEdge> bag = new ArrayList<DirectedEdge>();
       for (int v = 0; v < V; v++)
           for (DirectedEdge e : adj[v])
               bag.add(e);
          return bag; 
    }
}

class DijkstraSP {
    private DirectedEdge[] edgeTo;
    private double[] distTo;
    private Map<Integer, Double> pq;

    public DijkstraSP(EdgeWeightedDigraph G, int s)
    {
        edgeTo = new DirectedEdge[G.V()];
        distTo = new double[G.V()];
        pq = new HashMap<Integer, Double>();
//        ValueComparator vc = new ValueComparator(pq);
//        TreeMap<Integer, Double> sortedSet = new TreeMap(vc);

        for (int v = 0; v < G.V(); v++)
           distTo[v] = Double.POSITIVE_INFINITY;

        distTo[s] = 0.0;
        pq.put(s, 0.0);

        while (!pq.isEmpty()) {
            ValueComparator vc = new ValueComparator(pq);
            TreeMap<Integer, Double> sortedSet = new TreeMap(vc);
            int minKey = sortedSet.firstKey();
            pq.remove(minKey);
            relax(G, minKey);
        }
     }

    private void relax(EdgeWeightedDigraph G, int v) {
       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;
             if (pq.containsKey(w)) 
                 pq.put(w, distTo[w]);
             else
                 pq.put(w, distTo[w]);
          }
       }
    }

    public double distTo(int v)
    {   return distTo[v];   }

    public boolean hasPathTo(int v)
    {   return distTo[v] < Double.POSITIVE_INFINITY;  }


    public Iterable<DirectedEdge> pathTo(int v)
    {
       if (!hasPathTo(v)) return null;
       Stack<DirectedEdge> path = new Stack<DirectedEdge>();
       for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()])
          path.push(e);
       return path;
  }

}


class ValueComparator implements Comparator<Integer> {
    Map<Integer, Double> base;
    public ValueComparator(Map<Integer, Double> base) {
        this.base = base;
    }

    public int compare(Integer a, Integer b) {
        if (base.get(a) > base.get(b)) {
            return -1;
        } else if(base.get(a) < base.get(b)) {
            return 1;
        } 
        return 0;
    }
}