Explanation: Node 0 is disconnected from the rest of the graph, so only node 0 is reachable.

Solution

Method 1 – Dijkstra's Algorithm with Edge Usage Tracking

Intuition

The key idea is to use Dijkstra's algorithm to find the maximum number of moves left when reaching each node, and for each edge, track how many new subdivided nodes can be reached from both sides. The answer is the sum of all reachable original nodes and all reachable subdivided nodes on each edge.

Approach

Build the graph as an adjacency list.
Use a max-heap to perform Dijkstra's algorithm, tracking the maximum moves left at each node.
For each edge, track how many subdivided nodes are reached from both ends.
The answer is the number of original nodes reached plus the sum over all edges of min(cnti, used from u + used from v).

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {\n        vector<vector<pair<int,int>>> g(n);\n        for (auto& e : edges) {\n            g[e[0]].emplace_back(e[1], e[2]);\n            g[e[1]].emplace_back(e[0], e[2]);\n        }\n        vector<int> moves(n, -1);\n        priority_queue<pair<int,int>> pq;\n        pq.emplace(maxMoves, 0);\n        while (!pq.empty()) {\n            auto [mv, u] = pq.top(); pq.pop();\n            if (moves[u] >= 0) continue;\n            moves[u] = mv;\n            for (auto& [v, cnt] : g[u]) {\n                int left = mv - cnt - 1;\n                if (left >= 0 && moves[v] < 0) pq.emplace(left, v);\n            }\n        }\n        int ans = 0;\n        for (int x : moves) if (x >= 0) ans++;\n        for (auto& e : edges) {\n            int a = moves[e[0]] < 0 ? 0 : moves[e[0]];\n            int b = moves[e[1]] < 0 ? 0 : moves[e[1]];\n            ans += min(e[2], a + b);\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> reachableNodes</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">>></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> edges</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> maxMoves</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> n</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<s

Related Tags