【华为419机考真题】树上逃离 or 猴子爬树

妖狐艹你老母 2023-09-30 23:42 20阅读 0赞

### 本篇题解：树上逃离 or 猴子爬树 ###

### 题目描述 ###

给定一棵树，这个树有  n n n 个节点，节点编号从  0 0 0 开始依次递增， 0 0 0 固定为根节点。  
在这棵树上有一个小猴子，初始时该猴子位于根节点（ 0 0 0号） 上，小猴子一次可以沿着树上的边从一个节点挪到另一个节点，但这棵树上有一些节点设置有障碍物，如果某个节点上设置了障碍物，小猴子就不能通过连接该节点的边挪动到该节点上。

问小猴子是否能跑到树的叶子节点（叶子节点定义为只有一条边连接的节点），如果可以，请输出小猴子跑到叶子节点的最短路径（通过的边最少），否则输出字符串 NULL。

### 输入 ###

第一行给出数字  n n n，表示这个树有  n n n 个节点，节点编号从  0 0 0开始依次递增， 0 0 0 固定为根节点， 1 < = n < 10000 1<=n<10000 1<=n<10000

第二行给出数字  e d g e edge edge，表示接下来有  e d g e edge edge 行，每行是一条边

接下来的  e d g e edge edge行是边： x y x y xy，表示  x x x 和  y y y 节点有一条边连接

接下来的一行给出数字  b l o c k block block，表示接下来有  b l o c k block block行，每行是个障碍物

接下来的  b l o c k block block 行是障碍物： x x x，表示节点  x x x 上存在障碍物。

### 输出 ###

如果小猴子能跑到树的叶子节点，请输出小猴子跑到叶子节点的最短路径(通过的边最少)

比如小猴子从 0 经过 1 到达 2 (叶子节点) ，那么输出 `0->1->2`，否则输出 `NULL`。

注意如果存在多条最短路径，请按照节点序号排序输出，比如 `0->1` 和 `0->3` 两条路径，第一个节点 `0` 一样，则比较第二个节点 `1` 和 `3`，`1` 比 `3` 小，因此输出 `0->1` 这条路径。  
再如 `0->5->2->3` 和 `0->5->1->4`，则输出 `0->5-31->4`

### 示例一 ###

### 输入 ###

4
    3
    0 1
    0 2
    0 3
    2
    2
    3

### 输出 ###

0->1

### 说明 ###

`n=4,edge=[[0,1],[0,2],[0,3]],block=[2,3]` 表示一个有 4 个节点、3 条边的树，其中节点 2 和节点 3 上有障碍物，小猴子能从 0 到达叶子节点 1 (节点 1 只有一条边\[1,0\]和它连接，因此是叶子节点) ，即可以跑出这个树，所以输出为 `0->1`。

### 示例二 ###

### 输入 ###

7
    6
    0 1
    0 3
    1 2
    3 4
    1 5
    5 6
    1

### 输出 ###

0->1->2

### 说明 ###

节点 4 上有障碍物，因此 `0-3-4` 这条路不通，节点 2 和节点 6 都是叶子节点，但 `0->1->2` 比 `0->1->5->6` 路径短(通过的边最少) ，因此输出为 `0->1->2`

### 示例三 ###

### 输入 ###

2
    1
    0 1
    1
    1

### 输出 ###

NULL

### 说明 ###

节点 1 是叶子节点，但存在障碍物，因此小猴子无法到达叶子节点，输出 NULL

### 示例四 ###

### 输入 ###

4
    3
    0 1
    0 2
    0 3
    1
    2

### 输出 ###

0->1

### 说明 ###

`n=4,edge=[[0,1],[0,2],[0,3]],block=[2]` 表示一个有 4 个节点、3 条边的树，其中节点 2 上有障碍物，小猴子能从 0 到达叶子节点 1 (节点 1 只有一条边\[0,1\]和它连接，因此是叶子节点) ，路径是 `0->1`，也能从 0 到达叶子节点 3(节点 3 只有一条边 `[0,3]` 和它连接，因此是叶子节点) ,路径是 `0->3`，因此按通过节点的顺序及序号比较选择 `0->1`。