leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

commit	f5a7b3222c3e691e5f16f087dfea040e10a0c14d
parent	3d9ab29390f6b2dc09a7c2a1c5a41f1964176289
author	Dimitrije Dobrota <mail@dimitrijedobrota.com>
date	Wed, 28 Jun 2023 15:10:03 +0200

Daily Problem Improved

Diffstat:

Problems/1514.cpp

++++++++++++++++++------------------------

1 files changed, 18 insertions(+), 24 deletions(-)

diff --git a/Problems/1514.cpp b/Problems/1514.cpp

@@ -1,39 +1,33 @@

class Solution {

struct edge {

int dest;

double w;

edge(int d, double w) : dest(d), w(w) {}

friend bool operator<(const edge &e1, const edge &e2) {

return e1.w < e2.w;

}

};

typedef tuple<double, int> edge;

public:

double maxProbability(int n, vector<vector<int>> &edges,

vector<double> &succProb, int start, int end) {

double maxProbability(int n, const vector<vector<int>> &edges,

const vector<double> &succProb, int start, int end) {

vector<vector<edge>> adj(n);

vector<int> visited(n, false);

vector<bool> visited(n, false);

vector<double> dist(n, 0);

priority_queue<edge> pq;

for (int i = 0; i < succProb.size(); i++) {

adj[edges[i][0]].push_back({edges[i][1], succProb[i]});

adj[edges[i][1]].push_back({edges[i][0], succProb[i]});

adj[edges[i][0]].push_back({succProb[i], edges[i][1]});

adj[edges[i][1]].push_back({succProb[i], edges[i][0]});

}

pq.push({start, dist[start] = 1.0});

for (int k = 0; k < n; k++) {

while (!pq.empty() && visited[pq.top().dest]) pq.pop();

if (pq.empty()) break;

edge c = pq.top();

pq.push({dist[start] = 1.0, start});

while (n && !pq.empty()) {

auto [w, dest] = pq.top();

pq.pop();

if (c.dest == end) return c.w;

visited[c.dest] = true;

for (edge &p : adj[c.dest])

if (!visited[p.dest] && dist[c.dest] * p.w > dist[p.dest]) {

dist[p.dest] = dist[c.dest] * p.w;

pq.push({p.dest, dist[p.dest]});

if (visited[dest]) continue;

if (dest == end) return w;

visited[dest] = true;

for (const auto &[pw, pd] : adj[dest]) {

if (!visited[pd] && dist[dest] * pw > dist[pd]) {

dist[pd] = dist[dest] * pw;

pq.push({dist[pd], pd});

}

n--;

}

return 0;