raghuvanshraj

1514.cpp

Aug 4th, 2021
684
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:   vulkan
  3.  *    created:  13.08.2020 09:58:18 PM
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. vector<double> dijkstra(vector<vector<pair<int, double>>> &adj_list, int u) {
  10.     int n = adj_list.size();
  11.     vector<double> probs(n, 0);
  12.     probs[u] = 1;
  13.     priority_queue<pair<double, int>> qu;
  14.     qu.push({1, u});
  15.     vector<bool> processed(n);
  16.     while (not qu.empty()) {
  17.         int x = qu.top().second;
  18.         qu.pop();
  19.         if (not processed[x]) {
  20.             processed[x] = true;
  21.             for (auto edge : adj_list[x]) {
  22.                 int y = edge.first;
  23.                 double wt = edge.second;
  24.                 if (probs[y] < probs[x] * wt) {
  25.                     probs[y] = probs[x] * wt;
  26.                     qu.push({probs[y], y});
  27.                 }
  28.             }
  29.         }
  30.     }
  31.  
  32.     return probs;
  33. }
  34.  
  35. double maxProbability(int n, vector<vector<int>> &edges, vector<double> &probs, int s, int e) {
  36.     int m = edges.size();
  37.     vector<vector<pair<int, double>>> adj_list(n);
  38.     for (int i = 0; i <= m - 1; ++i) {
  39.         adj_list[edges[i][0]].push_back({edges[i][1], probs[i]});
  40.         adj_list[edges[i][1]].push_back({edges[i][0], probs[i]});
  41.     }
  42.  
  43.     return dijkstra(adj_list, s)[e];
  44. }
  45.  
  46. int main(int argc, char const *argv[]) {
  47.     int n, m;
  48.     cin >> n >> m;
  49.     vector<vector<int>> edges(m, vector<int>(2));
  50.     vector<double> probs(m);
  51.     for (int i = 0; i <= m - 1; ++i) {
  52.         cin >> edges[i][0] >> edges[i][1];
  53.     }
  54.     for (int i = 0; i <= m - 1; ++i) {
  55.         cin >> probs[i];
  56.     }
  57.     int s, e;
  58.     cin >> s >> e;
  59.  
  60.     cout << maxProbability(n, edges, probs, s, e);
  61.  
  62.     return 0;
  63. }
RAW Paste Data