An interesting problem solved by Dijkstra

Dijkstra is an important algorithm can be used to solve the SSSP problem for graphs with positive weights. A template for can be found from here.

882. Reachable Nodes In Subdivided Graph

The above problem can be solved by using exactly the Dijkstra algorithm. The basic idea is:

1. build a graph by using the weight as the cnt for each edge
2. compute the shortest path from 0 to each node
3. then for each edge ab, from a to pick up the maximum number of available moves to the direction of ab; from b to pick up the maximum number of available moves to the direction of ba. Then sum them up if the sum is larger than the cnt, use the cnt.

Code

typedef pair<int, int> PII;
const int INF = 1<<30;
class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
        // build the graph
        vector<vector<PII>> graph(n);
        for (auto edge: edges){
            int u = edge[0], v = edge[1], cost = edge[2];
            graph[u].emplace_back(v, cost);
            graph[v].emplace_back(u, cost);
        }
        vector<int> dis(n, INF);
        dis[0] = 0;
        set<PII> pq;
        for (int i = 0; i < n; ++i){
            if (i == 0) pq.emplace(0, 0);
            else pq.emplace(INF, i);
        }
        while (!pq.empty()){
            // explore the shortest path sofa
            auto [cost, node] = *pq.begin(); pq.erase(pq.begin());
            for (auto [neighbor, weight] : graph[node]){
                if (dis[neighbor] > dis[node] + weight + 1){
                    // update 
                    // 1) remove old node info from pq
                    pq.erase(pq.find({dis[neighbor], neighbor}));
                    // 2) update the dis info
                   dis[neighbor] = dis[node] + weight + 1;
                    // 3) insert the updated node info to the pq
                     pq.emplace(dis[neighbor], neighbor);
                }  
            }
        }
        int ret = 0;
        for (auto edge: edges){
             int u = edge[0], v = edge[1], cnt = edge[2];
            int left = dis[u] == INF? 0 : max(0, maxMoves - dis[u]);
            int right = dis[v] == INF? 0 : max(0, maxMoves - dis[v]);
            int thisret = min(left + right, cnt);
            ret += thisret; 
        }
        for (auto x: dis) ret += x <= maxMoves;
        return ret;   
    }
};