Untitled
unknown
c_cpp
10 days ago
2.3 kB
6
Indexable
Never
#include <iostream> #include <vector> #include <algorithm> using namespace std; class WarehouseNetwork { vector<vector<pair<int, int>>> adjList; vector<int> values, distanceFromRoot; vector<vector<int>> ancestors; int n; void dfs(int node, int parent, int distance) { distanceFromRoot[node] = distance; ancestors[node].push_back(parent); for (auto &[nextNode, weight] : adjList[node]) { if (nextNode != parent) { dfs(nextNode, node, distance + weight); ancestors[node].insert(ancestors[node].end(), ancestors[nextNode].begin(), ancestors[nextNode].end()); } } } bool isCompatible(int u, int v) { if (find(ancestors[v].begin(), ancestors[v].end(), u) != ancestors[v].end() && distanceFromRoot[v] - distanceFromRoot[u] <= values[v]) { return true; } return false; } public: WarehouseNetwork(int nodes) : n(nodes) { adjList.resize(n); values.resize(n); distanceFromRoot.resize(n, 0); ancestors.resize(n); } void addRoad(int from, int to, int weight) { adjList[from].push_back({to, weight}); adjList[to].push_back({from, weight}); } void setValue(int node, int val) { values[node] = val; } long countCompatiblePairs() { long count = 0; dfs(0, -1, 0); for (int u = 0; u < n; ++u) { for (int v = u + 1; v < n; ++v) { if (isCompatible(u, v)) { ++count; } } } return count; } }; int main() { int nodes = 6; WarehouseNetwork network(nodes); vector<int> from = {1, 6, 1, 1, 4}; vector<int> to = {6, 5, 2, 4, 3}; vector<int> weight = {4, 1, 3, 2, 1}; vector<int> values = {2, 8, 3, 5, 4}; for (int i = 0; i < from.size(); ++i) { network.addRoad(from[i] - 1, to[i] - 1, weight[i]); } for (int i = 0; i < values.size(); ++i) { network.setValue(i, values[i]); } cout << "Number of compatible pairs: " << network.countCompatiblePairs() << endl; return 0; }
Leave a Comment