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[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;
}
};

Data Scientist/MLE/SWE @takemobi