Untitled

 avatar
unknown
plain_text
a year ago
3.6 kB
4
Indexable
public class Solution {
    public class Triplet1{
        int node;
        long w;
        int extra;
        public Triplet1(int n, long w, int e){
            this.node=n;
            this.w=w;
            this.extra=e;
        }
    }
    public class Triplet2{
        int node;
        long d;
        int extra;
        public Triplet2(int n, long d, int e){
            this.node=n;
            this.d=d;
            this.extra=e;
        }
    }
    public int solve(int A, int[][] B, int C, int D, int[][] E) {
        //approacH: Modified Dijkstra algo on graph consisiting of edges + extra edges . 
        //Maintain extra info about each edge i.e., 0/1 is it extra edge or not. 
        // Triplet1<node,w,extra> 
        //TC: O(MlogM + N)
        //SC: O(M+N)
        int n = A;
        int m = B.length; 
        int e = E.length; 
        int src = C , dest=D; 
        //maintain adj list. 
        ArrayList<ArrayList<Triplet1>> adj = new ArrayList<>(); 
        //initialize. 
        for(int i=0;i<=n;i++){
            adj.add(new ArrayList<Triplet1>());
        }
        //populate using B and E. 
        int u,v,w;
        for(int edge=0;edge<m;edge++){
            u=B[edge][0];
            v=B[edge][1];
            w=B[edge][2];
            adj.get(u).add(new Triplet1(v,w,0));
            adj.get(v).add(new Triplet1(u,w,0));
        }
        for(int edge=0;edge<e;edge++){
            u=E[edge][0];
            v=E[edge][1];
            w=E[edge][2];
            adj.get(u).add(new Triplet1(v,w,1));
            adj.get(v).add(new Triplet1(u,w,1));
        }
        //maintain dist array. 
        long[] dist = new long[n+1];
        //intialize to inf. 
        for(int i=0;i<=n;i++){
            dist[i]=Long.MAX_VALUE;
        }
        //maintain minHeap<Triplet2> 
        PriorityQueue<Triplet2> mh = new PriorityQueue<>( new Comparator<Triplet2>(){
            @Override 
            public int compare(Triplet2 a, Triplet2 b){
                if(a.d < b.d){
                    return -1;
                }else if(a.d > b.d){
                    return 1;
                }else{
                    return 1; 
                }
            }
        });
        //kick start process.
        dist[src]=0;
        mh.add(new Triplet2(src,0,0));
        Triplet2 min;
        Triplet1 nbr;
        int extra;  
        while(mh.isEmpty()==false){
            min = mh.peek(); 
            mh.remove(); 
            //System.out.printf("node: %d d: %d extra: %d dist[node]: %d %n",min.node,min.d,min.extra,dist[min.node]);
            //check if it's really best ? 
            if(dist[min.node]== min.d){
                //System.out.printf("inside %n");
                //explore all valid options. 
                for(int i=0;i<adj.get(min.node).size();i++){
                    nbr = adj.get(min.node).get(i);
                    extra = min.extra +  nbr.extra;
                    //System.out.printf("nbr node: %d extra: %d %n",nbr.node,extra);
                    if(extra <= 1 && (dist[nbr.node] > min.d + nbr.w) ){
                        //System.out.printf("inside neighbor%n");
                        dist[nbr.node]= min.d + nbr.w;
                        mh.add(new Triplet2(nbr.node,dist[nbr.node],extra));
                    }
                }
            } 
        }
        //check 
        if(dist[dest]==Long.MAX_VALUE){
            return -1;
        }else{
            return (int)dist[dest];
        }
    }
}
Leave a Comment