 # I hope i am able to make sense

#1
``````class Node{
public:
int to;
int wt;
Node(int to,int wt)
{
this->to=to;
this->wt=wt;
}
Node()
{
to=0;
wt=0;
}

};
class PQ_element{
public:
Node node;
int wt_till;
PQ_element(Node node,int wt_till)
{
this->node=node;
this->wt_till=wt_till;
}
};
struct compare{
bool operator()(PQ_element &n1,PQ_element & n2)
{
return n1.wt_till>n2.wt_till;
}
};

int dij(vector<vector<Node>>&Graph,int &C,int&D,vector<int>& visited)
{

priority_queue<PQ_element,vector<PQ_element>,compare> pq;

PQ_element ele=PQ_element(Node(C,0),0);
pq.push(ele);

while(pq.size())
{
PQ_element curr=pq.top();
Node n1=curr.node;
int pos=n1.to;
int cost=curr.wt_till;
pq.pop();
if(visited[pos]==1)
{
continue;
}
if(pos==D)
{
return cost;
}
visited[pos]=1;
for(Node e:Graph[pos])
{
if(!visited[e.to])
{
pq.push(PQ_element(Node(e),e.wt+cost));
}
}

}
return -1;

}

int Solution::solve(int A, vector<vector<int> > &B, int C, int D, vector<vector<int> > &E) {
vector<vector<Node>> Graph(100001,vector<Node>());

int l1=0;
for(int i=0;i<B.size();i++)
{
l1=max({B[i],B[i],l1});
Graph[B[i]].push_back(Node(B[i],B[i]));
// Graph[B[i]].push_back(Node(B[i],B[i]));

}
// vector<int> visited(A+1,0);
int ans=INT_MAX;
for(int i=0;i<E.size();i++)
{

//     int x=max(E[i];
//     if(x>Graph.size())
//   {
//         Graph.resize()

//   }
//  Making the new graph
Graph[E[i]].push_back(Node(E[i],E[i]));
Graph[E[i]].push_back(Node(E[i],E[i]));
l1=max({E[i],E[i],l1});

vector<int> visited(l1+1,0);

int a1=dij(Graph,C,D,visited);
// cout<<a1<<" ";
if(a1!=-1)
{
ans=min(ans,a1);
}

// Deleting that node from the graph
Graph[E[i]].pop_back();
Graph[E[i]].pop_back();

}
if(ans==INT_MAX)
{
return -1;
}
return ans;

}
``````

Hello
Here are some of my Comments:
Why am I making classes? At first it may seems good to interviewer and I feel more comfortable in class than pairs as, using class I can also print the path if I want.

``````        so I made 2 classes.
1.  Node : These are just Graph nodes, I could have used vector<int> also but whatever I prefer classes.
2.PQ_element: For using this In priority queue as it contains the current position and wt at current position.
``````

I applied Dijkstra and why not Prims or krushal?
So the reason is we need minimum path between 2 nodes primes and rushal gives MST but here this is not the case.

``````now about comparator: Why am I using n1.cur_wt > n2.cur_wt;

Okay I don't know which kind of priority queue is what I am just tired to
remember them So if we want minimum element at the top we should use a
comparator that first is greater than the second
then min heap will be there. Else If we want maximum
then use first< second ( opposite of what is used in sorting). Why bcoz we need to find
``````

`minimum sum path.`