# leetcode\_882

Starting with an undirected graph (the "original graph") with nodes from 0 to N-1, subdivisions are made to some of the edges.

The graph is given as follows: edges\[k] is a list of integer pairs (i, j, n) such that (i, j) is an edge of the original graph,

and n is the total number of new nodes on that edge.

Then, the edge (i, j) is deleted from the original graph, n new nodes (x\_1, x\_2, ..., x\_n) are added to the original graph,

and n+1 new edges (i, x*1), (x\_1, x\_2), (x\_2, x\_3), ..., (x*{n-1}, x\_n), (x\_n, j) are added to the original graph.

Now, you start at node 0 from the original graph, and in each move, you travel along one edge.

Return how many nodes you can reach in at most M moves.

```
Example 1:

Input: edges = [[0,1,10],[0,2,1],[1,2,2]], M = 6, N = 3
Output: 13
Explanation: 
The nodes that are reachable in the final graph after M = 6 moves are indicated below.

Example 2:

Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], M = 10, N = 4
Output: 23
```

## Note:

* 0 <= edges.length <= 10000
* 0 <= edges\[i]\[0] < edges\[i]\[1] < N
* There does not exist any i != j for which edges\[i]\[0] == edges\[j]\[0] and edges\[i]\[1] == edges\[j]\[1].
* The original graph has no parallel edges.
* 0 <= edges\[i]\[2] <= 10000
* 0 <= M <= 10^9
* 1 <= N <= 3000
* A reachable node is a node that can be travelled to using at most M moves starting from node 0.

## Solutions

* Treat the number of nodes within each edge as weights.

1. **dijkstra method**
2. `curw` denotes moved steps from the initial node.
3. The result is composed of two pairts, one is the number of real nodes traversed using shortest paths algorithm, another is the extra steps can be made along the edge within the constraint of `M`, each edge may be recorded two times from both sides.

```
    ->node1.............node2
        -> *****    **** <-
```

```cpp
class Solution {
public:
#define edge(n1, n2) ((n1) * N + (n2))
    int reachableNodes(vector<vector<int>>& edges, int M, int N) {
        using E = pair<int, int>;
        vector<vector<E>> g(N + 1);
        for (auto & e : edges) {
            g[e[0]].push_back({e[2], e[1]});
            g[e[1]].push_back({e[2], e[0]});
        }
        vector<int> costs(N + 1, M + 1);
        unordered_map<int, int> used;
        costs[0] = used[edge(0, 0)] = 0;
        priority_queue<E, vector<E>, greater<>> pq;
        pq.push({0, 0});

        int res = 0;
        while (pq.size()) {
            auto [curw, cur] = pq.top(); pq.pop();
            if (curw > costs[cur]) continue;
            res++;
            for (auto [w, out] : g[cur]) {
                used[edge(cur, out)] = min(w, M - curw);
                int neww = curw + w + 1;
                if (neww < min(costs[out], M + 1)) {
                    costs[out] = neww;
                    pq.push({neww, out});
                }
            }
        }

        for (auto & e : edges) {
            int n1 = e[0], n2 = e[1], w = e[2];
            res += min(w, used[edge(n1, n2)] + used[edge(n2, n1)]);
        }

        return res;
    }
};
```

or

```cpp
#define edge(x, y) (x < y ? x * N + y : y * N + x)

using E = pair<int, int>;
class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int M, int N) {
        unordered_map<int, vector<E>> g;
        unordered_map<int, vector<int>> mg;
        for (auto & e : edges) {
            // to make path sum equals to the number of visited nodes, we increment the number of inner nodes by 1. ie. after moved `num + 1` steps, we will be at the target node of this edge.
            g[e[0]].push_back({e[1], e[2] + 1});
            g[e[1]].push_back({e[0], e[2] + 1});
            mg[edge(e[0], e[1])] = {0, 0, e[2] + 1};
        }

        unordered_map<int, int> cost;
        // caution: Comp in priority queue is different from Comp in sort.
        auto cmp = [](E & e1, E & e2) {
            return e1.second > e2.second;
        };
        // min stack
        priority_queue<E, vector<E>, decltype(cmp)> pq(cmp);
        // the 0 node is counted in weight sum.
        pq.push({0, 0}); cost[0] = 0;
        int res = 0;

        while (!pq.empty()) {
            int cur = pq.top().first;
            int curw = pq.top().second;
            pq.pop();
            if (curw > cost[cur] || curw > M)
                continue;
            // curw may be equal to M, which means the current node is the last node
            res++;
            for (auto & e : g[cur]) {
                int next = e.first, neww = curw + e.second;
                auto & used = mg[edge(cur, next)][cur > next];
                used = max(used, min(e.second, M - curw));
                if (!cost.count(next) || neww < cost[next]) {
                    cost[next] = neww;
                    pq.push({next, neww});
                }
            }
        }
        // since the weight is incremented 1, we only count the number of inner nodes.
        for (auto & [ei, ev] : mg) {
            int used = ev[0] + ev[1];
            res += used >= ev[2] ? ev[2] - 1 : used;
        }

        return res;
    }
};
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhongquan789.gitbook.io/leetcode/leetcode/leetcode_882.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.