Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79
This question is updated on GFG , if you look at strivers screen its just asking path but in updated question you need to append the dist[n] also and then reverse
just do - reverse(path.begin(), path.end()); // Insert the total distance as the first element of the result path.insert(path.begin(), dist[n]); return path;
we can print the path with the help of distance array only (no need of parent array) if(dis[n]==1e9){ return {-1}; } vectorans; int curr_node=n; while(curr_node!=1){ ans.push_back(curr_node); for(auto it:al[curr_node]){ if(dis[it.first]==dis[curr_node]-it.second){ curr_node=it.first; } } } ans.push_back(1); reverse(ans.begin(),ans.end()); return ans;
Thanks a lot, striver. Ur content is far better than paid courses. U literally explained us everything in such a depth. Thanks again for all your amazing playlists.
I just love the confidence and the clarity with which you code the solution. I have started to recite the solution similar to your style while coding alone ^^
My approach similar to WordLadder-2, in set along with dist store currentList too... vector shortestPath(int n, int m, vector& edges) { // Code here vector adj[n+1]; for(int i=0; i
Hi sir, I solved this question by own and this is happened because of you. Before your videos graph is like impossible thing for me but now I can solve medium level questions easily
Another short approach using Dijkstra's Algorithm (in this we will store the path in priority queue itself just like word ladder II) vector shortestPath(int n, int m, vector& edges) { vector adj[n + 1]; for(auto e : edges) adj[e[0]].push_back({e[1], e[2]}), adj[e[1]].push_back({e[0], e[2]}); vector d(n + 1, INT_MAX); d[1] = 0; priority_queue pq; pq.push({0, {1}}); int minD = INT_MAX; vector ans = {-1}; while(pq.size()) { vector path = pq.top().second; int dis = pq.top().first; pq.pop(); int node = path.back(); if(node == n && minD > dis) minD = dis, ans = path; for(auto ad : adj[node]) { if(d[node] + ad.second < d[ad.first]) { d[ad.first] = d[node] + ad.second; path.push_back(ad.first); pq.push({d[ad.first], path}); path.pop_back(); } } } return ans; }
Question is updated in GFG, it is undirected so we need to add u->v and v->u both in the adjacency List. Also Need to add the dist[n] to the path and need to reverse it as the question is asking the dist and path of src to N node.
Hi Striver, With your hint I was able figure out that this algo is same as we used to print LIS/LCS in DP. Can't think of anyone teaching DSA better than you. Well its not wrong to say that you are the Netflix of DSA xD
We can also use pq of dist and the path we have so far to solve it without needing the parent array. vector shortestPath(int N, int m, vector& edges) { priority_queue pq ; vector dist(N+1,INT_MAX) ; vectoradj[N+1] ; for (int i =0 ; i< m ;i ++) { int u = edges[i][0] ; int v = edges[i][1]; int wt =edges[i][2] ; adj[u].push_back({v,wt}) ; adj[v].push_back({u,wt}) ; } pq.push({0,{1}}) ; //bool flag = false ; while(!pq.empty()) { auto x = pq.top() ; pq.pop() ; vector path = x.second ; int node = path.back(); int dis = x.first ; if (node==N) { // flag = true ; return path ; } for (auto x : adj[node]) { int adjNode = x.first ; int adjDis = x.second ; if (dist[adjNode]>adjDis+dis) { dist[adjNode] = adjDis + dis ; path.push_back(adjNode); pq.push({adjDis + dis, path}); path.pop_back(); } } } return {-1} ; }
Was able to come up with the solution without watching the video. Here's my implementation : vector shortestPath(int n, int m, vector& edges) { // Code here vectoradj[n+1]; for(int i = 0 ; i < edges.size() ; i++){ adj[edges[i][0]].push_back({edges[i][1],edges[i][2]}); adj[edges[i][1]].push_back({edges[i][0],edges[i][2]}); } priority_queue pq; pq.push({0,{1,{1}}}); vectordist(n+1,INT_MAX); dist[1]=0; while(!pq.empty()){ pair ki=pq.top(); pq.pop(); int dis=ki.first; int k=ki.second.first; vectorvec=ki.second.second; vectorvy=vec; if(k==n) return vec;
for(int i = 0 ; i < adj[k].size() ; i++){ if(dis+adj[k][i][1]
Understood Suggestion:- ek sath itne sare video mat upload karo channel ke reach Kam hoti hai Ho sake to ek ek hour ke video schedule kardo And amazing approach striver Bhai 😀 Edit:- mai galat tha #keep_striving
As the note not yet updated. Just for resource : java code public static List shortestPath(int n, int m, int edges[][]) { ArrayList adj = new ArrayList(); for(int i = 0;i
hey Striver bhaiya, i have a doubt that instead of storing the parents, can't we do this. if anyone else can help , then please. int node = n; while(node != 1){ for(auto it : adj[node]){ int adj_node = it.first; int adj_wt = it.second; if(dist[node] == dist[adj_node] + adj_wt){ ans.push_back(adj_node); node = adj_node; } } } intution is simple that whose adjNode's distance + weight gives the node's distance will be the parent node.
hey striver , I solved this problem using a different approach where my pq consists of distance and vector(containing path until now) runs just fine class Solution { public: vector shortestPath(int n, int m, vector& edges) { // Code here vectorans; vectoradj[n+1]; for(int i=0;i
Hey instead of using extra array of parent can't we store a Pair in the dist array itself and do the backtrack from there. This way we can save some space.
How can it have a better time complexity?, If observed closely the total number of integers will be equal, so I don't think it's better from any angle.
No it's based on graph If you want smallest path (or) all paths then store parent=list of set of values Ex:parent=[0,{1, 2}] dist=[0,1] Again if we get dist 1 of index 1 from other path then simply add that node to parent [1] then apply dfs not while loop.
One doubt! Why we need to initialise parent[ ] with idx themselves? does it help in anyway? my all test cases were passed without doing that (I did on Java ) because if the given graph is a NULL graph then each node is a parent of itself,it doesn't make a diiference here since we only want the path if initial vertex and final vertex is connected,but at the end of the program doing this yields us the correct parent array no matter weather path exists or not
Here's the Java Code:- class Solution { class pair{ int v; int w; pair(int v,int w){ this.v = v; this.w = w; } } class pqpair{ int distance; int node; pqpair(int distance,int node){ this.distance = distance; this.node = node; } } public List shortestPath(int n, int m, int edges[][]) { // Code Here. ArrayList adj = new ArrayList(); for(int i=0;i
One doubt! Why we need to initialise parent[ ] with idx themselves? does it help in anyway? my all test cases were passed without doing that (I did on Java )
because if the given graph is a NULL graph then each node is a parent of itself,it doesn't make a diiference here since we only want the path if initial vertex and final vertex is connected,but at the end of the program doing this yields us the correct parent array no matter weather path exists or not
why we need to push 5 at the end to run this code on gfg vector shortestPath(int n, int m, vector& edges) { vector adj[n+1]; for(auto it:edges){ adj[it[0]].push_back({it[1],it[2]}); adj[it[1]].push_back({it[0],it[2]}); }
Because they asked for the shortest distance value as well. So, they want you to first give them the shortest distance as the first index then the graph path.
class Solution { static class Node { int node, distance; public Node(int node, int distance) { this.node = node; this.distance = distance; } } static class Pair implements Comparable{ int distance, node; public Pair(int distance, int node) { this.distance = distance; this.node = node; } public int compareTo(Pair o) { return this.distance - o.distance; } } public static List shortestPath(int n, int m, int edges[][]) { // code here ArrayList adjList = new ArrayList(); for(int i=0;i
understood Even if my result and expected result is same its not passing test case. Test case number - 63 pin this comment so everyone can save their time Your Code's output is: 1 46 11 51 It's Correct output is: 1 46 11 51 Output Difference 1 46 11 51
JAVA Solution class Pair implements Comparable{ int src; int wt; public Pair(int src, int wt){ this.src = src; this.wt = wt; } public int compareTo(Pair pair){ return this.wt - pair.wt; } } class Node{ int dest; int cost; public Node(int dest, int cost){ this.dest = dest; this.cost = cost; } } class Solution { public static List shortestPath(int n, int m, int edges[][]) { int memo[] = new int[n+1]; int distance[] = new int[n+1]; PriorityQueue pq = new PriorityQueue(); ArrayList graph = new ArrayList(); for(int i = 0; i
very easy approach vector shortestPath(int n, int m, vector& edges) { // CREATE ADJACENECY MATRIX vectoradj[n+1]; for(auto i:edges){ int a=i[0]; int b=i[1]; int c=i[2]; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } // display(adj,n); sets; //DISTANCE , NODE vectordis(n+1,INT_MAX); unordered_mappar; s.insert({0,1}); dis[1]=0; while(!s.empty()){ auto temp=*(s.begin()); int a=temp.first; // DISTANCE int b=temp.second; // NODE s.erase({a,b}); for(auto i:adj[b]){ int x=i.first; // NODE int y=i.second; // WEIGHT int nd=a+y; if(nd
I've understood the algo and the code but it's showing TLE error in gfg for last 2 cases, both with priority_queue and set...anyone else having same problem as me ?
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79
This question is updated on GFG , if you look at strivers screen its just asking path but in updated question you need to append the dist[n] also and then reverse
yeah, i was confused where's the error in my code , then did this and passed all tetscases. Thanks!!
Thanks for sharing 👍
just do -
reverse(path.begin(), path.end());
// Insert the total distance as the first element of the result
path.insert(path.begin(), dist[n]);
return path;
@@prakharm614 thanks buddy if u dont mind can you give me ur discord...
💫
Thanks a lot was confused about this!!!
we can print the path with the help of distance array only (no need of parent array)
if(dis[n]==1e9){
return {-1};
}
vectorans;
int curr_node=n;
while(curr_node!=1){
ans.push_back(curr_node);
for(auto it:al[curr_node]){
if(dis[it.first]==dis[curr_node]-it.second){
curr_node=it.first;
}
}
}
ans.push_back(1);
reverse(ans.begin(),ans.end());
return ans;
Thanks a lot, striver. Ur content is far better than paid courses. U literally explained us everything in such a depth. Thanks again for all your amazing playlists.
Solved this code without watching any approach in this video just when he said try it out first, i go and solved it. Thanks Striver.
I just love the confidence and the clarity with which you code the solution. I have started to recite the solution similar to your style while coding alone ^^
My approach similar to WordLadder-2, in set along with dist store currentList too...
vector shortestPath(int n, int m, vector& edges) {
// Code here
vector adj[n+1];
for(int i=0; i
NOTE
Now the question is updated ,we also have to pushback the weight of shortest path.
typedef pair pip;
vector shortestPath(int n, int m, vector& edges) {
vector< pair >adj[n+1];
for(auto &it : edges)
{
adj[it[0]].push_back({it[1],it[2]});
adj[it[1]].push_back({it[0],it[2]});
}
priority_queue< pip, vector , greater< pip > >pq;
pq.push({0,1});
vectordist(n+1,1e9);
dist[1] = 0;
vectorparent(n+1);
for(int i = 1;i 0)
{
auto it = pq.top();
int node = it.second;
int dis = it.first;
pq.pop();
for(auto &it : adj[node])
{
int adjnode = it.first;
int edgeweight = it.second;
if(dis + edgeweight < dist[adjnode])
{
dist[adjnode] = dis + edgeweight;
pq.push({dis+edgeweight , adjnode});
parent[adjnode] = node;
}
}
}
if(dist[n] == 1e9) return {-1};
vectorpath;
int node = n;
while(parent[node] != node)
{
path.push_back(node);
node = parent[node];
}
path.push_back(1);
path.push_back(dist[n]);
reverse(path.begin(),path.end());
return path;
}
it's showing tle error in the last test case
Thank you so much!!! Was struggling to find my mistake!
@@bhaktisharma9681 did u find the solution ?? Then pls share it here 🙏
Can you explain the code for graph creation? I'm not able to understand it
@@vaisakh5802 Watch initial videos of the series and understand how adjacency list maintains its adjacent nodes and weight
Hi sir, I solved this question by own and this is happened because of you. Before your videos graph is like impossible thing for me but now I can solve medium level questions easily
after line 20 we should push pair {0,1} initially to priority queue
you can but here we push {0,1} as we store in pq and we store in adj list hope you get this
Using that parent array was indeed a smart move 😀 !!
Another short approach using Dijkstra's Algorithm (in this we will store the path in priority queue itself just like word ladder II)
vector shortestPath(int n, int m, vector& edges) {
vector adj[n + 1];
for(auto e : edges) adj[e[0]].push_back({e[1], e[2]}), adj[e[1]].push_back({e[0], e[2]});
vector d(n + 1, INT_MAX);
d[1] = 0;
priority_queue pq;
pq.push({0, {1}});
int minD = INT_MAX;
vector ans = {-1};
while(pq.size()) {
vector path = pq.top().second;
int dis = pq.top().first; pq.pop();
int node = path.back();
if(node == n && minD > dis) minD = dis, ans = path;
for(auto ad : adj[node]) {
if(d[node] + ad.second < d[ad.first]) {
d[ad.first] = d[node] + ad.second;
path.push_back(ad.first);
pq.push({d[ad.first], path});
path.pop_back();
}
}
}
return ans;
}
damn nice 🔥
Great soln!!
same approach but tle on tc 4
Solved this without watching the video. Took 2 hours but was worth it.
simple solution again.. thanks Striver. This Graph series feels easier than any other..❤
GFG Apparantly have updated the testcases and this solution no longer is getting accepted
you just have to append the shortest path distance at the beginning of the answer array
TreeSet solution in Java (Just need to override compareTo, equals and hashCode methods of the SortedSet interface):
class Pair implements Comparable{
int node, dist;
public Pair(int dist, int node){
this.node = node;
this.dist = dist;
}
@Override
public boolean equals(Object e){
Pair other = (Pair) e;
return node == other.node;
}
@Override
public int hashCode(){
return node;
}
@Override
public int compareTo(Pair p){
if(p.dist == this.dist)
return this.node - p.node;
return this.dist - p.dist;
}
}
class Solution
{
static int[] dijkstra(int V, ArrayList graph, int S)
{
//dist, node -> sort by smaller distance from src. If dist same, then sort by smaller node
TreeSet set = new TreeSet();
set.add(new Pair(0, S));
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[S] = 0;
while(!set.isEmpty()){
Pair cur = set.pollFirst();
int src = cur.node, distToSrc = cur.dist;
for(ArrayList edge : graph.get(src)){
int dest = edge.get(0), curDist = edge.get(1);
if(dist[dest] > distToSrc + curDist){
dist[dest] = distToSrc + curDist;
set.add(new Pair(dist[dest], dest));
}
}
}
return dist;
}
}
Understood! Such a wonderful explanation as always, thank you very much!!
Question is updated in GFG, it is undirected so we need to add u->v and v->u both in the adjacency List.
Also Need to add the dist[n] to the path and need to reverse it as the question is asking the dist and path of src to N node.
Hi Striver, With your hint I was able figure out that this algo is same as we used to print LIS/LCS in DP. Can't think of anyone teaching DSA better than you. Well its not wrong to say that you are the Netflix of DSA xD
same same
which year?
And I solved it seeing ur hint (print LIS problem in dp)
@@krishanpratap3286 2020 passed out lol
So are you looking to switch?
We can also use pq of dist and the path we have so far to solve it without needing the parent array.
vector shortestPath(int N, int m, vector& edges) {
priority_queue pq ;
vector dist(N+1,INT_MAX) ;
vectoradj[N+1] ;
for (int i =0 ; i< m ;i ++) {
int u = edges[i][0] ;
int v = edges[i][1];
int wt =edges[i][2] ;
adj[u].push_back({v,wt}) ;
adj[v].push_back({u,wt}) ;
}
pq.push({0,{1}}) ;
//bool flag = false ;
while(!pq.empty()) {
auto x = pq.top() ;
pq.pop() ;
vector path = x.second ;
int node = path.back();
int dis = x.first ;
if (node==N) {
// flag = true ;
return path ;
}
for (auto x : adj[node]) {
int adjNode = x.first ;
int adjDis = x.second ;
if (dist[adjNode]>adjDis+dis) {
dist[adjNode] = adjDis + dis ;
path.push_back(adjNode);
pq.push({adjDis + dis, path});
path.pop_back();
}
}
}
return {-1} ;
}
one major doubt. How can we come up with these kind of solutions on our own???
Practice, and practice...
because if you just keep practicing with closed eyes it would take an eternity to become a good problem solver.....
@@SatyamEdits Thank you
@@takeUforward Thank you
Aa jata hai bro if you practice many questions
Just love ur way of solution Problem ❤️❤️
*Problem Solution
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Please use a proper compiler which shows output also so it will be more understandable.
We basically hashing the node for each updatation in the distances[adjNode]. I guess we can use HashMap too in this case.
Was able to come up with the solution without watching the video. Here's my implementation :
vector shortestPath(int n, int m, vector& edges) {
// Code here
vectoradj[n+1];
for(int i = 0 ; i < edges.size() ; i++){
adj[edges[i][0]].push_back({edges[i][1],edges[i][2]});
adj[edges[i][1]].push_back({edges[i][0],edges[i][2]});
}
priority_queue pq;
pq.push({0,{1,{1}}});
vectordist(n+1,INT_MAX);
dist[1]=0;
while(!pq.empty()){
pair ki=pq.top();
pq.pop();
int dis=ki.first;
int k=ki.second.first;
vectorvec=ki.second.second;
vectorvy=vec;
if(k==n) return vec;
for(int i = 0 ; i < adj[k].size() ; i++){
if(dis+adj[k][i][1]
almost same type of solution but got tle on case 4
Thank you So much Striver !
Your Code's output is:
1 46 11 51
It's Correct output is:
1 46 11 51
Output Difference
1 46 11 51
😂😂😂
what if we need to find all the shortest paths from src to destination? (eg if there are 3 paths from src->dest with total wt=5,how to get all three)
What if there are multiple shortest path and we have to print all of them? In that case what should we do?
Masterpiece Explanation
Litterly saved me, deserves a subscription if you ask me!!!
Understood! amazing Explanation.
how to handle multiple shorest path . This question was asked in my college intership OA of atlassian. PLss tell how to handle ?
My Attempt ->
vector shortestPath(int n, int m, vector& edges) {
vector adjList(n+1);
vector distances(n+1,{INT_MAX,vector{}});
distances[1] = {0,{1}};
for(int i=0;i distances[node].first) continue;
vector path = distances[node].second;
for(auto pair : adjList[node]){
int adjNode = pair.first;
int d = pair.second;
if(distances[adjNode].first > d + dist) {
distances[adjNode].first = d + dist;
vector newPath = path;
newPath.push_back(adjNode);
distances[adjNode].second = newPath;
pq.push({d + dist, adjNode});
}
}
}
vector result;
if(distances[n].first == INT_MAX) return {-1};
else {
result.push_back(distances[n].first);
for(auto node : distances[n].second) result.push_back(node);
return result;
}
}
I am unable to find this Question on GFG
Same
Huge effort 🤩
Understood Bhaiya
Understood
Suggestion:- ek sath itne sare video mat upload karo channel ke reach Kam hoti hai
Ho sake to ek ek hour ke video schedule kardo
And amazing approach striver Bhai 😀
Edit:- mai galat tha
#keep_striving
Areh pdhai ki channel ki reach hoti v nai h, word of mouth pe hi chalta h
@@takeUforward true
@@takeUforward still if u upload 1 or 2 video daily that will make us consistent
Thank you very much. You are a genius.
understood, thanks for the great video
Understood sir thankyou❤✨🙏🙇♂
As the note not yet updated.
Just for resource : java code
public static List shortestPath(int n, int m, int edges[][]) {
ArrayList adj = new ArrayList();
for(int i = 0;i
hey Striver bhaiya, i have a doubt that instead of storing the parents, can't we do this.
if anyone else can help , then please.
int node = n;
while(node != 1){
for(auto it : adj[node]){
int adj_node = it.first;
int adj_wt = it.second;
if(dist[node] == dist[adj_node] + adj_wt){
ans.push_back(adj_node);
node = adj_node;
}
}
}
intution is simple that whose adjNode's distance + weight gives the node's distance will be the parent node.
Thank you sir 🙏
we dont have to initialize the whole parent array, just do parent [source] = source ;
hey striver , I solved this problem using a different approach where my pq consists of distance and vector(containing path until now) runs just fine
class Solution {
public:
vector shortestPath(int n, int m, vector& edges) {
// Code here
vectorans;
vectoradj[n+1];
for(int i=0;i
UNDERSTOOD.
TLE on the last test case?
if the weight of both edges is same, we need to handle that based on nodes in Priority Queue
UnderStood Sir!
Hey instead of using extra array of parent can't we store a Pair in the dist array itself and do the backtrack from there. This way we can save some space.
#tuf and take forward for crowdwork...#leetcode more solution needed
How can it have a better time complexity?, If observed closely the total number of integers will be equal, so I don't think it's better from any angle.
lol, pair of size n is nothing but two arrays of size n clubbed together.
Hi striver, can the datatype of distance array be a class which stores node distance and parent ? so that we will not take two separate arrays?
its 3:54 am and busy creating my future😁😄
Sir you forgot the case of returning list of -1s if path's not possible
understood, thank you so much.
Understood 👍
What if there are two shortest path 1->2->4->5 and 1->3->5 with the same dist value , will it print 1->3->5?
No it's based on graph
If you want smallest path (or) all paths then store parent=list of set of values
Ex:parent=[0,{1, 2}] dist=[0,1]
Again if we get dist 1 of index 1 from other path then simply add that node to parent [1] then apply dfs not while loop.
Very much helpful 😍😍
understood bhaiya
UNDERSTOOD
Understood 😇
Understood❤
One doubt! Why we need to initialise parent[ ] with idx themselves? does it help in anyway? my all test cases were passed without doing that (I did on Java )
because if the given graph is a NULL graph then each node is a parent of itself,it doesn't make a diiference here since we only want the path if initial vertex and final vertex is connected,but at the end of the program doing this yields us the correct parent array no matter weather path exists or not
doesn't matter what you store at the parent caue when you will get the path it will automatically get updated with the new parents.
Thank you bhaiya
Here's the Java Code:-
class Solution {
class pair{
int v;
int w;
pair(int v,int w){
this.v = v;
this.w = w;
}
}
class pqpair{
int distance;
int node;
pqpair(int distance,int node){
this.distance = distance;
this.node = node;
}
}
public List shortestPath(int n, int m, int edges[][]) {
// Code Here.
ArrayList adj = new ArrayList();
for(int i=0;i
Huge love from south❤
just amazing !!
One doubt! Why we need to initialise parent[ ] with idx themselves? does it help in anyway? my all test cases were passed without doing that (I did on Java )
because if the given graph is a NULL graph then each node is a parent of itself,it doesn't make a diiference here since we only want the path if initial vertex and final vertex is connected,but at the end of the program doing this yields us the correct parent array no matter weather path exists or not
understtooooddddd
Understood!
Understood!!
adj[it[0]] is a pair, how can we do a push_back to a pair??
Always remember, where you are coming from!
nice:) explanation sir
understood
Golden❤
why cant we take max priority queue? its giving tle .
understood💙💙💙
why we need to push 5 at the end to run this code on gfg
vector shortestPath(int n, int m, vector& edges) {
vector adj[n+1];
for(auto it:edges){
adj[it[0]].push_back({it[1],it[2]});
adj[it[1]].push_back({it[0],it[2]});
}
priority_queue pq;
vector dist(n+1,1e9);
vector parent(n+1);
for(int i=1;i
Because they asked for the shortest distance value as well. So, they want you to first give them the shortest distance as the first index then the graph path.
what about no path case (-1)?
Understood
“understood”
mujhe ye question striver's sheet me q nhi dikh raha :-\
class Solution {
static class Node {
int node, distance;
public Node(int node, int distance) {
this.node = node;
this.distance = distance;
}
}
static class Pair implements Comparable{
int distance, node;
public Pair(int distance, int node) {
this.distance = distance;
this.node = node;
}
public int compareTo(Pair o) {
return this.distance - o.distance;
}
}
public static List shortestPath(int n, int m, int edges[][]) {
// code here
ArrayList adjList = new ArrayList();
for(int i=0;i
same
Where can we find the java code for this video
am i missing something?
since its undirected graph there definitely exists a path right?
then y print (-1)
What if the Node is Unreachable ?
@@gamerversez5372 undirected graph means it's reachable every where.
Also there is only one component
i am not able to write code by myself what to do?
can someone share link of question , it seems to be broken
understood
Even if my result and expected result is same its not passing test case. Test case number - 63
pin this comment so everyone can save their time
Your Code's output is:
1 46 11 51
It's Correct output is:
1 46 11 51
Output Difference
1 46 11 51
same here
glitch hai, ab working
THank you
amazing
understood
sir
JAVA Solution
class Pair implements Comparable{
int src;
int wt;
public Pair(int src, int wt){
this.src = src;
this.wt = wt;
}
public int compareTo(Pair pair){
return this.wt - pair.wt;
}
}
class Node{
int dest;
int cost;
public Node(int dest, int cost){
this.dest = dest;
this.cost = cost;
}
}
class Solution {
public static List shortestPath(int n, int m, int edges[][]) {
int memo[] = new int[n+1];
int distance[] = new int[n+1];
PriorityQueue pq = new PriorityQueue();
ArrayList graph = new ArrayList();
for(int i = 0; i
very easy approach
vector shortestPath(int n, int m, vector& edges) {
// CREATE ADJACENECY MATRIX
vectoradj[n+1];
for(auto i:edges){
int a=i[0];
int b=i[1];
int c=i[2];
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
// display(adj,n);
sets; //DISTANCE , NODE
vectordis(n+1,INT_MAX);
unordered_mappar;
s.insert({0,1});
dis[1]=0;
while(!s.empty()){
auto temp=*(s.begin());
int a=temp.first; // DISTANCE
int b=temp.second; // NODE
s.erase({a,b});
for(auto i:adj[b]){
int x=i.first; // NODE
int y=i.second; // WEIGHT
int nd=a+y;
if(nd
look at this
vector shortestPath(int n, int m, vector& edges) {
// Code here
vectoradj[n+1];
for(auto it:edges)
{
adj[it[0]].push_back({it[1],it[2]});
adj[it[1]].push_back({it[0],it[2]});
}
queueq;
q.push(1);
vectordis(n+1,1e9);
dis[1]=0;
vectorvec(n+1);
vectortemp;
vec[1]={1};
while(q.size()!=0)
{
int node=q.front();
vectort=vec[node];
q.pop();
for(auto i:adj[node])
{
if(dis[i.first]>dis[node]+i.second)
{
dis[i.first]=dis[node]+i.second;
temp=t;
temp.push_back(i.first);
q.push(i.first);
vec[i.first]=temp;
}
}
}
if(vec[n].size()==0)return {-1};
else return vec[n];
}
awesome
Please anyone tell me from where could I learn the use of priority queue of min heap in java
gfg
For same code but using unordered map insted of vector for getting path is giving me tle on 7th testcase itself😮!! Can anyone tell me the reason
I've understood the algo and the code but it's showing TLE error in gfg for last 2 cases, both with priority_queue and set...anyone else having same problem as me ?
Yes, I solved it alone and got TLE using Java. But when I solved it using C++ it ran well!!