Leetcode 882. Reachable Nodes In Subdivided Graph

Posted on | In |

Starting with an undirected graph (the “original graph”) with nodes from 0 to N-1, subdivisions are made to some of the edges.

The graph is given as follows: edges[k] is a list of integer pairs (i, j, n) such that (i, j) is an edge of the original graph,

and n is the total number of new nodes on that edge.

Then, the edge (i, j) is deleted from the original graph, n new nodes (x_1, x_2, …, x_n) are added to the original graph,

and n+1 new edges (i, x_1), (x_1, x_2), (x_2, x_3), …, (x_{n-1}, x_n), (x_n, j) are added to the original graph.

Now, you start at node 0 from the original graph, and in each move, you travel along one edge.

Return how many nodes you can reach in at most M moves.

Example 1:

Input: edges = [[0,1,10],[0,2,1],[1,2,2]], M = 6, N = 3

Output: 13

Explanation:

The nodes that are reachable in the final graph after M = 6 moves are indicated below.

Example 2:

Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], M = 10, N = 4

Output: 23

Note:

0 <= edges.length <= 10000

0 <= edges[i][0] < edges[i][1] < N

There does not exist any i != j for which edges[i][0] == edges[j][0] and edges[i][1] == edges[j][1].

The original graph has no parallel edges.

0 <= edges[i][2] <= 10000

0 <= M <= 10^9

1 <= N <= 3000

A reachable node is a node that can be travelled to using at most M moves starting from node 0.

思路

求最短路径(Dij算法)
给定源点的血量
相当于求从源点到其他顶点剩余的最大值(至少要大于0)
有的顶点可能到达不了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int reachableNodes(vector<vector<int>>& edges, int M, int N) {
        //节点，对应的最大血量
        unordered_map<int,int> HP;
        //节点编号->相邻点(->边的权值)
        unordered_map<int,unordered_map<int,int>> g_;
        for(auto e:edges){
            g_[e[0]][e[1]]=e[2];
            g_[e[1]][e[0]]=e[2];
        }
        //hp->node
        priority_queue<pair<int,int>> pq;
        pq.push({M,0});
        while(!pq.empty()){
            pair<int,int> p=pq.top();
            pq.pop();
            int hp=p.first;
            int cur=p.second;
            if(HP.count(cur)) continue;
            HP[cur]=hp;
            for(auto tt:g_[cur]){
                int next_hp=hp-tt.second-1;
                int nxt=tt.first;
                //!!
                if(HP.count(nxt)||next_hp<0) continue;
                pq.push({next_hp,nxt});
            } 
        }
        int ans=HP.size();
        for(auto e:edges){
           int m=HP.count(e[0])?HP[e[0]]:0;
           int n=HP.count(e[1])?HP[e[1]]:0;
             ans+=min(e[2],m+n);
        }
        
        return ans;
        
    }
};