Version: v0.0.0-...-899dd15 Latest Latest Go to latest
Published: Sep 11, 2020 License: MIT

## README ¶

### 882. Reachable Nodes In Subdivided Graph

#### 题目

Starting with anundirected 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,nnew nodes (x_1, x_2, ..., x_n) are added to the original graph,

and n+1 newedges (i, x_1), (x_1, x_2), (x_2, x_3), ..., (x_{n-1}, x_n), (x_n, j)are added to the originalgraph.

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

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:

1. 0 <= edges.length <= 10000
2. 0 <= edges[i] <edges[i] < N
3. There does not exist anyi != j for which edges[i] == edges[j] and edges[i] == edges[j].
4. The original graphhas no parallel edges.
5. 0 <= edges[i] <= 10000
6. 0 <= M <= 10^9
7. 1 <= N <= 3000
8. A reachable node is a node that can be travelled tousing at mostM moves starting fromnode 0.

## Documentation ¶

### Constants ¶

This section is empty.

### Variables ¶

This section is empty.

### Functions ¶

This section is empty.

### Types ¶

#### type PQ ¶

`type PQ [][]int`

PQ implements heap.Interface and holds entries.

#### func (PQ) Len ¶

`func (pq PQ) Len() int`

#### func (PQ) Less ¶

`func (pq PQ) Less(i, j int) bool`

#### func (*PQ) Pop ¶

`func (pq *PQ) Pop() interface{}`

Pop 从 pq 中取出最优先的 entry

#### func (*PQ) Push ¶

`func (pq *PQ) Push(x interface{})`

Push 往 pq 中放 entry

#### func (PQ) Swap ¶

`func (pq PQ) Swap(i, j int)`