Untitled
unknown
plain_text
a year ago
3.8 kB
6
Indexable
#include "color_walk.hpp" using namespace cs251; class priority_queue { private : std:: vector <std:: pair <int, int>> m_arr; int m_size = 0; void bottom_up(int index) { if (index == 0) { return; } int par = (index-1)/2; if(m_arr[par] > m_arr[index]) { std:: pair <int, int> temp = m_arr[par]; m_arr[par] = m_arr[index]; m_arr[index] = temp; bottom_up(par); } } void top_down(int index){ int left = (2 * index) + 1; int right = (2 * index) + 2; if (left >= m_size) { return; } int min_index = index; if (m_arr[index]> m_arr[left]) { min_index = left; } if ((right < m_size) && (m_arr[index] > m_arr[right])) { min_index = right; } if (min_index != index) { std:: pair <int, int> temp = m_arr[min_index]; m_arr[min_index] = m_arr[index]; m_arr[index] = temp; top_down(min_index); } } public : void push (std:: pair <int, int> node){ m_arr.push_back(node); m_size++; bottom_up(m_size); } void pop(){ std:: pair <int, int> temp = m_arr[0]; m_arr[0] = m_arr[m_size - 1]; m_arr[m_size - 1] = temp; m_arr.pop_back(); m_size--; top_down(0); } std:: pair <int, int> top(){ return m_arr[0]; } int size() { return m_size; } bool empty() { return m_size == 0; } }; std::vector<std::pair<char, int>> color_walk::calculate(const graph& g, const handle startHandle) { // TODO: Implement color walk //throw std::logic_error("color_walk::" + std::string(__FUNCTION__) + "() not implemented"); int n = g.graph_vertices; std:: vector <graph_vertex> adj_list = g.read_graph(); /* for (int i = 0; i < adj_list.size(); i++) { std:: cout << i << " -> "; for (int j = 0; j < adj_list[i].m_edges.size(); j++) { std:: cout << "{" << adj_list[i].m_edges[j].m_destinationHandle << ", " << adj_list[i].m_edges[j].m_weight << " }, "; } std:: cout << "\n"; } */ std:: vector <long long> dist(3*n, 1e15); dist[startHandle] = 0; dist[startHandle + n] = 0; dist[startHandle + (2*n)] = 0; priority_queue pq; pq.push({0, startHandle}); pq.push({0, startHandle + n}); pq.push({0, startHandle + (2*n)}); while (!pq.empty()) { int node = pq.top().second; int d = pq.top().first; pq.pop(); for (int i=0; i < adj_list[node].m_edges.size(); i++) { int v = adj_list[node].m_edges[i].m_destinationHandle; int w = adj_list[node].m_edges[i].m_weight; color c = adj_list[node].m_edges[i].col; if (d + w <= dist[v]){ dist[v] = d + w; pq.push({dist[v], v}); } } } std:: vector <std::pair<char, int>> answer (n, {'-', -1}); answer[startHandle].second = 0; for (int i = 1; i < n; i++) { long long min_dist = 1e12; char from = '-'; /* if(dist[i] < min_dist) { min_dist = dist[i]; from = 'B'; } */ if(dist[i+n] < min_dist) { min_dist = dist[i+n]; from = 'R'; } if(dist[i+ 2*n] < min_dist) { min_dist = dist[i + 2*n]; from = 'G'; } if(dist[i] < min_dist) { min_dist = dist[i]; from = 'B'; } if (min_dist > 1e10) { continue; } answer[i] = {from, min_dist}; } return answer; }
Editor is loading...
Leave a Comment