Untitled

mail@pastecode.io avatar
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