Best possible solution in the world


#1

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;
pq.push({0,start});
d[start]=0;
while(!pq.empty())
{
int cur=pq.top().second;

    pq.pop();
    for(auto it:adj[cur])
    {
        if(d[it.first]>d[cur]+it.second)
        {
            d[it.first]=d[cur]+it.second;
            pq.push({d[it.first],it.first});
        }
    }
}

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

vector<vector<pair<int,int>>>adj(A+1);
for(int i=0;i<B.size();i++)
{
    adj[B[i][0]].push_back({B[i][1],B[i][2]});
    adj[B[i][1]].push_back({B[i][0],B[i][2]});
}
vector<int>ds(A+1,10000000);
vector<int>de(A+1,10000000); // not using INT_MAX becuase the dist variable (used below) will go out of bounds
dijikstra(ds,adj,C);
dijikstra(de,adj,D);

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];
    ans=min(ans,min(dist,dist1));
}

if(ans!=10000000)
return ans;
return -1;

}


#2

Wow it is a amazing solution


#3

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.


#4

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


#5

wow amazing solution


#6

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.


#7

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😼


#8

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


#9

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.


#10

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!!


#11

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