You are viewing a single comment's thread. Return to all comments →
Simple C++ solution using BFS.
long roadsAndLibraries(int n, int c_lib, int c_road, vector<vector<int>> cities) { if (c_lib <= c_road) return (long)n * (long)c_lib; unordered_map<int, vector<int>> cities_map(cities.size() * 2); for (auto& c : cities) { cities_map[c[0]].push_back(c[1]); cities_map[c[1]].push_back(c[0]); } long total_cost = 0; queue<int> qu; vector<char> visited(n+1, 0); for (int i = 1; i <= n; i++) { if (!visited[i]) { total_cost += (long)c_lib; visited[i] = 1; qu.push(i); while(!qu.empty()) { int city = qu.front(); qu.pop(); for (int other : cities_map[city]) { if (!visited[other]) { total_cost += (long)c_road; qu.push(other); visited[other] = 1; } } } } } return total_cost; }
Seems like cookies are disabled on this browser, please enable them to open this website
Roads and Libraries
You are viewing a single comment's thread. Return to all comments →
Simple C++ solution using BFS.