Description

Submission

class Solution {
    using pii = pair<int, int>;
public:
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        vector<int> dist(n, INT_MAX/2);
        unordered_map<int, unordered_map<int, int>> graph;

        for(auto& e: edges) {
            graph[e[0]][e[1]] = e[2] + 1;
            graph[e[1]][e[0]] = e[2] + 1;
        }

        priority_queue<pii, vector<pii>, greater<>> pq;
        pq.push({0, 0});
        while(!pq.empty()) {
            auto [t, cur] = pq.top();
            pq.pop();

            if(t >= dist[cur]) continue;
            dist[cur] = t;

            for(auto [nxt, d]: graph[cur]) {
                int newDist = d + t;
                if(newDist < dist[nxt]) {
                    pq.push({newDist, nxt});
                }
            }
        }

        int ret = n;
        for(int i = 0; i < n; ++i) {
            if(dist[i] > maxMoves) {
                ret--;
                continue;
            }
            int maxCover = maxMoves - dist[i];
            for(auto& [nxt, d]: graph[i]) {
                int cover = min(maxCover, d - 1);
                d -= cover;
                graph[nxt][i] -= cover;
                ret += cover;
            }
        }

        return ret;
    }
};