 # 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, v = edge, w = edge;
8.             graph[u].push_back({v, w});
9.             graph[v].push_back({u, w});
10.         }
11.
12.         map<int, int> dist;
13.         dist = 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, v = edge, w = edge;
55.             ans += min(w, used[{u, v}] + used[{v, u}]);
56.         }
57.         return ans;
58.     }
59. };
RAW Paste Data