Advertisement
i_love_rao_khushboo

Untitled

Aug 15th, 2022
827
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.71 KB | None | 0 0
  1. #define ll long long
  2. #define ld long double
  3. #define ull unsigned long long
  4. #define pb push_back
  5. #define ppb pop_back
  6. #define pf push_front
  7. #define ppf pop_front
  8. #define mp make_pair
  9. #define F first
  10. #define S second
  11. #define PI 3.1415926535897932384626
  12. #define sz(x) ((int)(x).size())
  13. #define vset(v, n, val) v.clear(); v.resize(n, val)
  14.  
  15. typedef pair<int, int> pii;
  16. typedef pair<ll, ll> pll;
  17. typedef vector<int> vi;
  18. typedef vector<ll> vll;
  19. typedef vector<ull> vull;
  20. typedef vector<bool> vb;
  21. typedef vector<char> vc;
  22. typedef vector<string> vs;
  23. typedef vector<pii> vpii;
  24. typedef vector<pll> vpll;
  25. typedef vector<vi> vvi;
  26. typedef vector<vll> vvll;
  27. typedef vector<vull> vvull;
  28. typedef vector<vb> vvb;
  29. typedef vector<vc> vvc;
  30. typedef vector<vs> vvs;
  31.  
  32. const double eps = 1e-11;
  33.  
  34. class Solution {
  35. public:
  36.    
  37.     // to store the input graph
  38.     vector<vector<pair<int, double>>> g;
  39.  
  40.     // n = #vertices, m = #edges in the input graph
  41.     int n, m;
  42.  
  43.     double dijkstra_modified(int src, int dst) {
  44.         // d[i] stores the maximum success probability of ith node from given src
  45.         vector<double> d(n);
  46.  
  47.         // to keep track of visited nodes
  48.         vb vis(n, 0);
  49.  
  50.         // initialising the distances of all nodes from src as infinity
  51.         for(int i = 0; i < n; i++) d[i] = 0.0;
  52.  
  53.         // the maximum success probability of src from itself = 1.0
  54.         d[src] = 1.0;
  55.  
  56.         // priority queue (max heap) to repeatedly find out the node having
  57.         // maximum success probability from src
  58.         priority_queue<pair<double, int>> q;
  59.  
  60.         // inserting the src to initialise the process
  61.         q.push({1.0, src});
  62.  
  63.         while(!q.empty()) {
  64.             // extract the node which is currently at minimum distance from src
  65.             int v = q.top().S;
  66.             double mx = q.top().F;
  67.             q.pop();
  68.            
  69.             if(v == dst) return mx;
  70.            
  71.             if(vis[v] or abs(mx - 0.0) <= eps) continue;
  72.             vis[v] = true;
  73.  
  74.             for(auto x: g[v]) {
  75.                 if((mx * x.S) > d[x.F]) {
  76.                     d[x.F] = mx * x.S;
  77.                     q.push({d[x.F], x.F});
  78.                 }
  79.             }
  80.         }
  81.        
  82.         return 0.0;
  83.     }
  84.    
  85.     double maxProbability(int nodes, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
  86.         n = nodes;
  87.         m = sz(edges);
  88.        
  89.         g.clear(); g.resize(n);
  90.        
  91.         for(int i = 0; i < m; i++) {
  92.             int x = edges[i][0], y = edges[i][1]; double wt = succProb[i];
  93.             g[x].pb({y, wt});
  94.             g[y].pb({x, wt});
  95.         }
  96.                
  97.         return dijkstra_modified(start, end);
  98.     }
  99. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement