nikunjsoni

882

Sep 12th, 2021
629
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define pii pair<int, int>
  2. class Solution {
  3. public:
  4.     int reachableNodes(vector<vector<int>>& edges, int M, int N) {
  5.         vector<vector<pii>> graph(N);
  6.         for(vector<int> edge: edges) {
  7.             int u = edge[0], v = edge[1], w = edge[2];
  8.             graph[u].push_back({v, w});
  9.             graph[v].push_back({u, w});
  10.         }
  11.  
  12.         map<int, int> dist;
  13.         dist[0] = 0;
  14.         for(int i = 1; i < N; ++i)
  15.             dist[i] = M+1;
  16.  
  17.         map<pii, int> used;
  18.         int ans = 0;
  19.  
  20.         priority_queue<pii, vector<pii>, greater<pii>> pq;
  21.         pq.push({0, 0});
  22.  
  23.         while (!pq.empty()) {
  24.             pii top = pq.top();
  25.             pq.pop();
  26.             int d = top.first, node = top.second;
  27.             if(d > dist[node]) continue;
  28.  
  29.             // Each node is only visited once.  We've reached
  30.             // a node in our original graph.
  31.             ans++;
  32.             for(auto pair: graph[node]) {
  33.                 // M - d is how much further we can walk from this node;
  34.                 // weight is how many new nodes there are on this edge.
  35.                 // v is the maximum utilization of this edge.
  36.                 int nei = pair.first;
  37.                 int weight = pair.second;
  38.                 used[{node, nei}] = min(weight, M - d);
  39.  
  40.                 // d2 is the total distance to reach 'nei' (neighbor) node
  41.                 // in the original graph.
  42.                 int d2 = d + weight + 1;
  43.                 if(d2 < min(dist[nei], M+1)) {
  44.                     pq.push({d2, nei});
  45.                     dist[nei] = d2;
  46.                 }
  47.             }
  48.         }
  49.  
  50.         // At the end, each edge (u, v, w) can be used with a maximum
  51.         // of w new nodes: a max of used[u, v] nodes from one side,
  52.         // and used[v, u] nodes from the other.
  53.         for (vector<int> edge: edges) {
  54.             int u = edge[0], v = edge[1], w = edge[2];
  55.             ans += min(w, used[{u, v}] + used[{v, u}]);
  56.         }
  57.         return ans;
  58.     }
  59. };
RAW Paste Data