Please Share dijkstra's algorithm questions

1
2 Likes
2

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

3

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

2 Likes
4

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

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

1 Like
5

This was a nice question.

2 Likes
6

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

1 Like
7 
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
8

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
9

Can’t seem to figure this question

10

REFER THIS

11

This was a nice problem

2 Likes
12

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

1 Like
13

TLE in in 2nd last subtask , @aneee004 @l_returns help
q : https://cses.fi/problemset/task/1671
HERE is my solution

14

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
15

Yes I tried with global too same issue :sleepy:

16

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
17

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

1 Like
18

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

19

Now I have experience with map and unordered_map as well :sweat_smile:

2 Likes
20

please help @carre