#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;
// Function to check if a subset of companies satisfies the distance constraint
bool isValidSubset(const vector<int>& companies, const unordered_map<int, vector<pair<int, int>>>& graph, int minDist, const vector<int>& nodeCompanies) {
unordered_set<int> nodes;
// Gather all nodes owned by the selected companies
for (int company : companies) {
for (size_t i = 0; i < nodeCompanies.size(); ++i) {
if (nodeCompanies[i] == company) nodes.insert(i + 1);
}
}
// Check pairwise distances between nodes
for (int node : nodes) {
queue<pair<int, int>> q; // Pair of {current node, distance from start}
unordered_set<int> visited;
q.push({node, 0});
visited.insert(node);
// Perform BFS to calculate distances from the current node
while (!q.empty()) {
auto [current, dist] = q.front();
q.pop();
// Check neighbors
for (const auto& [neighbor, weight] : graph.at(current)) {
if (!visited.count(neighbor)) {
if (nodes.count(neighbor) && dist + weight < minDist) {
return false; // Distance requirement violated
}
visited.insert(neighbor);
q.push({neighbor, dist + weight});
}
}
}
}
return true;
}
// Main function to calculate the number of valid subsets
int countValidSubsets(int graph_node, const vector<int>& graph_from, const vector<int>& graph_to,
const vector<int>& weights, int minDist, const vector<int>& companies) {
// Step 1: Build the graph
unordered_map<int, vector<pair<int, int>>> graph;
for (size_t i = 0; i < graph_from.size(); ++i) {
int u = graph_from[i], v = graph_to[i], w = weights[i];
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
// Step 2: Generate subsets of companies
int companyCount = *max_element(companies.begin(), companies.end());
int validSubsetCount = 0;
for (int mask = 1; mask < (1 << companyCount); ++mask) {
vector<int> subset;
for (int i = 0; i < companyCount; ++i) {
if (mask & (1 << i)) {
subset.push_back(i + 1); // Convert 0-based index to company number
}
}
// Step 3: Check if the subset is valid
if (isValidSubset(subset, graph, minDist, companies)) {
++validSubsetCount;
}
}
return validSubsetCount;
}
int main() {
// Hardcoded inputs
int graph_node = 4; // Number of nodes
vector<int> graph_from = {1,2,1,1}; // From nodes
vector<int> graph_to = {2,3,3,4}; // To nodes
vector<int> weights = {2,1,3,10}; // Weights of edges
int minDist = 2; // Minimum distance requirement
vector<int> companies = {1,2,3,2}; // Company assigned to each node
// Count the valid subsets
int result = countValidSubsets(graph_node, graph_from, graph_to, weights, minDist, companies);
cout << "Number of valid subsets: " << result << endl;
return 0;
}
Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}