# Untitled

unknown
plain_text
21 days ago
3.6 kB
3
Indexable
Never
```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;
//initialize.
for(int i=0;i<=n;i++){
}
//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];
}
for(int edge=0;edge<e;edge++){
u=E[edge][0];
v=E[edge][1];
w=E[edge][2];
}
//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;
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.
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;
}
}
}
}
//check
if(dist[dest]==Long.MAX_VALUE){
return -1;
}else{
return (int)dist[dest];
}
}
}
```