# 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

Data Scientist/MLE/SWE @takemobi