Untitled
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