import java.util.Set;
import java.util.Map;
import java.util.TreeMap;

public class DGraph {

    // If there is an edge (u,v), then edges.get(u).get(v) is its cost.
    private Map<String,Map<String,Integer>> edges;

    private String source; // this is the starting vertex for distances
    private Map<String,Integer> d;  // this stores the distances
    private Map<String,String> p;  // this stores the predecessors

    public DGraph(){
        edges = new TreeMap<String,Map<String,Integer>>();
    }

    private void ensureVertexExists(String v){
        if(!edges.containsKey(v)){
            edges.put(v, new TreeMap<String,Integer>()); // no out edges yet
        }
    }

    public void addEdge(String v1, String v2, int cost){
        ensureVertexExists(v1);
        ensureVertexExists(v2);
        edges.get(v1).put(v2,cost);
        d = null;  // change in graph invalidates any previous calculations
        p = null;
    }

    public void setSource(String start){
        ensureVertexExists(start);
        source = start;
        d = null; // change in source invalidates any previous calculations
        p = null;
    }

    public Set<String> vertices(){
        return edges.keySet();
    }

    private void calculate(){
        d = new TreeMap<String,Integer>();
        p = new TreeMap<String,String>();
        // THIS IS WHERE YOU NEED TO PUT DIJKSTRA'S ALGORITHM
        // TO FILL IN d AND p.
    }

    public int getDistance(String destination){
        // returns Integer.MAX_VALUE if the destination is unreachable
        if(source == null){
            throw new Error("Can't get distance without setting source.");
        }
        if(d == null){
            calculate();
        }
        if(d.containsKey(destination)){
            return d.get(destination);
        } else {
            return Integer.MAX_VALUE;
        }
    }

    public String getPredecessor(String destination){ // or null if none
        if(source == null){
            throw new Error("Can't get predecessor without setting source.");
        }
        if(p == null){
            calculate();
        }
        return p.get(destination);
    }
}