Please Share dijkstra's algorithm questions

2 Likes

https://cp-algorithms.com/graph/dijkstra.html

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

2 Likes

https://cses.fi/problemset/task/1671

https://cses.fi/problemset/task/1194

1 Like

This was a nice question.

2 Likes

https://leetcode.com/problems/cheapest-flights-within-k-stops/

1 Like
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
         vector<pair<int,double>>adj[n];
         for(int i=0;i<edges.size();i+=1){
             adj[edges[i][0]].push_back({edges[i][1] , succProb[i]});
             adj[edges[i][1]].push_back({edges[i][0] , succProb[i]});
         }
    
        
    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();
        
        for(auto xt : adj[u]){
            
            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 :joy:.

2 Likes

Can’t seem to figure this question

REFER THIS
https://www.quora.com/What-is-the-most-simple-efficient-C++-code-for-Dijkstras-shortest-path-algorithm

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
q : https://cses.fi/problemset/task/1671
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 :sleepy:

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 :relieved:.

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 :sweat_smile:

2 Likes

please help @carre