diff options
1 files changed, 20 insertions, 18 deletions
| -rw-r--r-- | Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW2-Zigzag.cpp | 38 |
diff --git a/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW2-Zigzag.cpp b/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW2-Zigzag.cpp index 57efbf6..1e007d8 100644 --- a/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW2-Zigzag.cpp +++ b/Year 2/Design and analysis of algorithms/Practicum/Homeworks/HW2-Zigzag.cpp @@ -7,33 +7,35 @@ using namespace std; long long N, M; typedef pair<long long, long long> Edge; +// Performance improvement - Static array and different neighbour vectors for bigger and smaller pair<vector<Edge>, vector<Edge>> graph[100005] = { { vector<Edge>(), vector<Edge>() } }; -bool visited[100005] = { false }; -typedef pair<Edge, bool> Qedge; +// Performance improvement? - Edge& rather than Edge +typedef pair<Edge&, bool> Qedge; + long long dijkstra(long long s) { - priority_queue<Qedge, vector<Qedge>, greater<Qedge>> q; - vector<bool> visitedlt(N, false); - vector<bool> visitednlt(N, false); - vector<long long> distlt(N, 0); - vector<long long> distnlt(N, 0); + // Performance improvement - queue rather than priority_queue + queue<Qedge> q; + // Wrong answer on multiple tests - remove visited logic + + // Performance improvement - from vector to statis array + // Wrong answer on a couple of tests - not init with { 0 } + long long distlt[100005] = { 0 }; + long long distnlt[100005] = { 0 }; distlt[s] = distnlt[s] = 0; - q.push({{ 0, s }, true}); + Edge b = { 0, s }; + q.push({b, true}); while (!q.empty()) { - auto c = q.top().first; - bool lt = q.top().second; + auto c = q.front().first; + bool lt = q.front().second; q.pop(); - if (lt) visitedlt[c.second] = true; - else visitednlt[c.second] = true; for (Edge& e : (lt) ? graph[c.second].second : graph[c.second].first) { - if (e.second == 0 || e.second== c.second || - (!lt && visitedlt[e.second]) || - (lt && visitednlt[e.second])) continue; + if (e.second == 0 || e.second == c.second) continue; // cout << "From: " << c.second+1 << " To: " << e.second+1 << endl; - vector<long long>& dist = (lt) ? distlt : distnlt, distc = (!lt) ? distlt : distnlt; - long long nd = distc[c.second] + e.first; - if ((dist[e.second] == 0 || nd < dist[e.second])) { + long long (&dist)[100005] = (lt) ? distlt : distnlt; + long long nd = ((!lt) ? distlt[c.second] : distnlt[c.second]) + e.first; + if (dist[e.second] == 0 || nd < dist[e.second]) { dist[e.second] = nd; q.push({ e, !lt }); } |