# 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.

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, v = edge, cost = edge;            graph[u].emplace_back(v, cost);            graph[v].emplace_back(u, cost);        }        vector<int> dis(n, INF);        dis = 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, v = edge, cnt = edge;            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;       }};`

Data Scientist/MLE/SWE @takemobi

Data Scientist/MLE/SWE @takemobi