Best possible solution in the world


void dijikstra(vector&d,vector<vector<pair<int,int>>>&adj,int start)
priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>> > pq;

    for(auto it:adj[cur])

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

for(int i=0;i<B.size();i++)
vector<int>de(A+1,10000000); // not using INT_MAX becuase the dist variable (used below) will go out of bounds

int ans=ds[D];
for(int i=0;i<E.size();i++)
    int dist=ds[E[i][0]]+de[E[i][1]]+E[i][2];
    int dist1=ds[E[i][1]]+de[E[i][0]]+E[i][2];

return ans;
return -1;



Wow it is a amazing solution


why are we taking a minimum of dist and dist1 when it is always true that dist will be less than dist1.
I might be wrong with that assumption so can you please explain to me why do we need to take a minimum of both.


Because distance here depends on weights of edges and not the actual distance that you are visualising


wow amazing solution


all the edges in array B are one directional but you have considered them as bi-directional
so In some cases your code give wrong answer.

3 // total no of nodes are 2
2 3 2 1 4 2 3 100 // one edge from 2 to 1 of weight 4 and second edge from 2 to 3 of wright 100
1 // source
2 // destination
1 3 3 2 100 // one extra edges from 3 to 2 of weight 100

your code is giving ans 4 (because u have considered edges present in B as bidirectional) but expexcted output for this testcase is -1 because there is no edge from 1 to 2 .

this problem can be solved by creating two graphs
first graph is as given in form of array B and apllying dijkshtra from source
second graph is reverse of given graph and apply dijkshtra from destination

then same approach as u have done.


Kindly submit my code and see for yourself , it works fine.
I took the edges in array B bidirectional because in many of the comments on discussion thread it was written that they have considered those edges as bidirectional
Still if you want you can make them unidirectional , you just have to comment out one line in my code. Do it and become a codeninja😼


Can you just tell me thought process and intitution i know it will definitely work i just want to know how you thought


you’re right. I tried both ways, keeping two graph one original and other as reversed and then following same procedure works. But considering all edges unidirectional doesn’t pass all test cases.


You failed to understand just one little thing that the path B is directed and in editorial they have taken “two diffrent adjencies” to store shrtest distance of points from “source” and from “destination”!! And directed nature of B is the reason you are modifying the existing paths by connecting x–>y and y–>x from graph E to check if this gives a minimum distance further!! Observe carefullytry to understand what i said, and u 'd definitely get it! So, ur this code is bound to fail many test case nd if not failing then it is due weak test cases!! Use 2 different adj to travel from each side!!


I know what you guys are saying exactly but when I did that I was getting wrong answer so I did this