Created
July 12, 2020 09:23
-
-
Save joechenrh/e9e792b2be6a5e5c3f7b14d5f2981843 to your computer and use it in GitHub Desktop.
dijkstra template
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct cmp | |
{ | |
bool operator()(const pair<int,double>& a, const pair<int,double>& b)const | |
{ | |
return a.second > b.second; | |
} | |
}; | |
class Solution { | |
public: | |
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& dists, int start, int end) { | |
vector<vector<pair<int, double>>> m(n); | |
for(int i = 0; i < edges.size(); ++i) { | |
auto &edge = edges[i]; | |
m[edge[0]].emplace_back(edge[1], dists[i]); | |
m[edge[1]].emplace_back(edge[0], dists[i]); | |
} | |
vector<double> dis(n, 10000000); | |
dis[start] = 0.0; | |
priority_queue<pair<int, double>,vector<pair<int, double>>, cmp> q; | |
q.emplace(start, 0.0); | |
int i, j; | |
double d, dij; | |
while(!q.empty()) { | |
std::tie(i, d) = q.top(); | |
q.pop(); | |
for (auto [j, pij] : m[i]) { | |
if(d + dij < dis[j]) { | |
dis[j] = d + dij; | |
q.emplace(j, dis[j]); | |
} | |
} | |
} | |
return prob[end]; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment