leetcode

0 class Solution {

1 public:

2 vector<int> countPairsOfConnectableServers(const vector<vector<int>> &edges,

3 const int signalSpeed) const {

4 const int n = size(edges) + 1;

5 vector<vector<pair<int, int>>> adj(n);

6

7 for (const auto &edge : edges) {

8 adj[edge[0]].emplace_back(edge[1], edge[2]);

9 adj[edge[1]].emplace_back(edge[0], edge[2]);

10 }

11

12 static int cnt[1001], res[1001];

13 stack<tuple<int, int, int>> st;

14

15 memset(res, 0x00, n * sizeof(*res));

16 for (int i = 0; i < n; i++) {

17 memset(cnt, 0x00, sizeof(cnt));

18 for (int j = 0; j < size(adj[i]); j++) {

19 st.emplace(i, adj[i][j].first, adj[i][j].second);

20

21 while (!st.empty()) {

22 const auto [p, c, t] = st.top();

23 st.pop();

24 if (t % signalSpeed == 0) cnt[j]++;

25 for (const auto [n, w] : adj[c]) {

26 if (n == p) continue;

27 st.emplace(c, n, t + w);

28 }

29 }

30

31 for (int k = 0; k < j; k++)

32 res[i] += cnt[j] * cnt[k];

33 }

34 }

35

36 return vector<int>(res, res + n);

37 }

38 };