 # Please Share dijkstra's algorithm questions

2 Likes

U can try this one too : https://leetcode.com/contest/weekly-contest-197/problems/path-with-maximum-probability/

2 Likes
1 Like

This was a nice question.

2 Likes
1 Like
``````class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
for(int i=0;i<edges.size();i+=1){
}

double prob[n];
for(int i=0;i<n;i++)
prob[i] = 0.0000;

prob[start] = 1;

// max priority queue
priority_queue<pair<double , int> > pq;

pq.push(make_pair(1,start));

while(!pq.empty()){

int u  = pq.top().second;

pq.pop();

int v = xt.first;

double weight = xt.second;

if(prob[v] < (prob[u] * weight) )
{
prob[v] = prob[u] * weight;

pq.push(make_pair(prob[v] , v));
}

}

}

return( prob[end] );

}
};

``````

Yes , but it is just plain Dijikistra with max prirority queue

1 Like

Yes! But I didn’t really solve many questions using Dijkstra’s, so it didn’t strike the moment I read the question. So I was trying my own implementation using dfs first and then a dp, and then finally realised what I’m trying to do is actually Dijkstra’s .

2 Likes

Can’t seem to figure this question

This was a nice problem

2 Likes

This problem has multiple solutions, one of them is Dijkstra’s. This disucuss entry might be helpful.

1 Like

TLE in in 2nd last subtask , @aneee004 @l_returns help
HERE is my solution

I’m not entirely sure if an array of vectors is passed by reference or by value. Did you try this with a global adjacency list?

Because everything else seems to be prefect.

1 Like

Yes I tried with global too same issue Okay, this might be a very very long shot, can you try using int instead of lli? (wherever lli is not necessary).
There are some very rare cases where using lli gives TLE. @therealnishuz has experience .

2 Likes

No , It will give me WA , already tried , after all try I ask here .

1 Like

I have too , sometimes (in Polynomial hashing ) , LLI give TLE and boom long int passes.

Now I have experience with `map` and `unordered_map` as well 2 Likes