在线评测链接:P1196 (opens new window)
# 题目内容
塔子哥居住在数据结构之城，如果将这个城市的路口看做点，两个路口之间的路看做边，那么该城市的道路能够构成一棵由市中心路口向城市四周生长的树，树的叶子节点即是出城口。
塔子哥今天想要出城办事，但不巧的是，有几个路口堵车了，塔子哥无法从一个正常的路口前往堵车的路口。假定塔子哥从一个正常的路口出发，请问塔子哥能否顺利出城（到达出城口）？如果可以，请帮塔子哥找到最省油的路径（经过路口最少的路径），否则请输出“”。
# 输入描述
第一行给出数字，表示这个城市有个路口，路口从开始依次递增，固定为根节点，
第二行给出数字，表示接下来有行，每行是一条道路
接下来的行是边: x，y，表示x和路口有一条道路连接。保证是一颗树
道路信息结束后接下来的一行给出数，表示接下菜有行，每行是一个堵车的路口
接下来的行是堵车路口，表示路口已堵车
# 输出描述
如果塔子哥能够顺利出城，请输出塔子哥能够到达任意一个出城口的最短路径（通过路口最少），比如塔子哥从经过到达 (出城口) ，那么输出“”;否则输出“”。注意如果存在多条最短路径，请按照节点序号排序输出，比如$ 0->1$ 和 两条路径，第一个节点一样，则比较第二个节点和，比小，因此输出这条路径。再如和$ 0->5->1->4$，则输出 。
# 样例
输入
4
3
0 1
0 2
0 3
2
2
3
输出
0->1
说明
, , 表示一个有个节点，条边的树，其中节点和节点上有障碍物，小猴子都能从到达叶子节点（节点1只有一条边和它连接，因此也是叶子节点），即可以跑出这个树，所以输出为.
# 样例2
输入
7
6
0 1
0 3
1 2
3 4
1 5
5 6
1
4
输出
0->1->2
说明
节点上有障碍物，因此这条路不通，节点和节点都是叶子节点，但比路径短 (通过的边最少) ，因此输出为。
# 思路
# 树上dfs/bfs
题意化简:给定一棵树，其中有些点无法访问。需要找一条从根节点到叶子结点的路径，要求满足长度最短且字典序最小。
# 做法1:dfs
直接dfs，在这个过程中存储好已访问的路径。然后遇到叶子结点就用当前路径更新答案路径。
这样做的复杂度是 ， 其中第一项来自于dfs的开销，第二项来自于 <在叶子结点的记录答案>的开销。但这里塔子哥不太会估计第二项的上界。感觉上是去构造一颗完全二叉树，这样复杂度是的
# 做法2:bfs
由于要满足长度最短，所以想到bfs也是比较自然的。对于字典序最小的性质，我们只需要对同一层的结点编号进行升序排序即可。复杂度
# 类似题目推荐
# LeetCode
# CodeFun2000
1.P1224 携程 2023.04.15-春招-第三题-魔法之树 (opens new window)
2.P1159. 2022年清华大学(深圳)保研夏令营机试题-第一题-树上计数 (opens new window)
3.P1196 华为 2023-04-19-第二题-塔子哥出城 (opens new window)
4.P1044. 拼多多内推笔试-2023.2.22.投喂珍珠 (opens new window)
5.P1193. 腾讯音乐 2023.04.13-暑期实习-第二题-价值二叉树 (opens new window)
# 代码
以下皆为做法。做法见题解区 (opens new window)
# CPP
#include<bits/stdc++.h>
#include <vector>
using namespace std;
int n, m;
vector<vector<int>> edges;
vector<int> blocks;
vector<int> path; // 当前路径
vector<int> res; // 答案路径
int tmp = INT_MAX;
vector<bool> used; // 标记是否被访问.
bool judge = false;
// idx 为当前所在点 , num 为深度
void dfs(int idx, int num){
// 到叶子节点，更新答案
if(edges[idx].size() == 0){
if(num < tmp){
tmp = num;
res = path;
}
judge = true;
}
//对同一层进行排序。这样保证了最先遇到的最短的答案也是字典序最小的
sort(edges[idx].begin(), edges[idx].end());
// 递归
for(auto & a : edges[idx]){
if(blocks[a] == 0 && used[a] == false){
used[a] = true;
path.push_back(a);
dfs(a, num + 1);
path.pop_back();
used[a] = false;
}
}
}
int main(){
// 读入
cin >> n >> m;
edges.resize(n + 1);
for(int i = 0; i < m; i ++){
int a, b;
cin >> a >> b;
edges[a].push_back(b);
}
// 标记 不能访问的点
int k;
cin >> k;
blocks.resize(n + 1, 0);
for(int i = 0; i < k; i ++){
int k1;
cin >> k1;
blocks[k1] = 1;
}
used.resize(n + 1, false);
path.push_back(0);
used[0] = true;
// dfs
dfs(0, 1);
// 输出
if(judge){
for(int i = 0; i < res.size(); i ++){
cout << res[i];
if(i != res.size() - 1){
cout << "->";
}
}
}
else cout << "NULL" << endl;
return 0;
}
# python
import sys
# 递归函数，idx 表示当前所在的节点，num 表示深度
def dfs(idx: int, num: int):
global tmp, path, res, judge
# 到达叶子节点，更新答案
if not edges[idx]:
if num < tmp:
tmp = num
res = path.copy() #列表复制
judge = True
# 对同一层进行排序。这样保证了最先遇到的最短的答案也是字典序最小的
edges[idx].sort()
# 递归搜索子节点
for a in edges[idx]:
if (blocks[a] == 0 and not used[a]):
used[a] = True
path.append(a)
dfs(a, num + 1)
path.pop() # 回溯
used[a] = False
# 读入
n = int(input())
m = int(input())
edges = [[] for i in range(n+1)]
for i in range(m):
a, b = map(int, sys.stdin.readline().strip().split())
edges[a].append(b)
# 标记不能访问的点
k = int(sys.stdin.readline().strip())
blocks = [0] * (n + 1)
for i in range(k):
k1 = int(sys.stdin.readline().strip())
blocks[k1] = 1
used = [False] * (n + 1)
path = [0]
used[0] = True
# dfs
tmp = 0x7fffffff # 设置一个最大值
res = []
judge = False
dfs(0, 1)
# 输出
if judge:
for i in range(len(res)):
print(res[i], end='')
if i != len(res) - 1:
print("->", end='')
else:
print("NULL", end='')
# Java
import java.util.*;
class Main {
static int ans=Integer.MAX_VALUE/2;
static ArrayList<Integer> path=new ArrayList<>();
static ArrayList<Integer> []map;
static boolean []arrive;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
//邻接表
map=(ArrayList<Integer>[]) new ArrayList<?>[n];
for(int i=0;i<n;i++){
map[i]=new ArrayList<Integer>();
}
int m=sc.nextInt();
for(int i=0;i<m;i++){
int a=sc.nextInt();
int b=sc.nextInt();
map[a].add(b);
}
// 每个节点的子节点排序
for(int i=0;i<n;i++){
if(map[i].size()!=0){
Collections.sort(map[i]);
}
}
int k=sc.nextInt();
//每个点是否可达
arrive=new boolean[n];
Arrays.fill(arrive, true);
for(int i=0;i<k;i++){
arrive[sc.nextInt()]=false;
}
// dfs求解
ArrayList<Integer> cur_path=new ArrayList<>();
cur_path.add(0);
dfs(0,cur_path);
if(ans!=Integer.MAX_VALUE/2){
for(int i=0;i<path.size()-1;i++){
System.out.printf("%d->",path.get(i));
}
System.out.println(path.get(path.size()-1));
}else{
System.out.println("NULL");
}
}
public static void dfs(int cur_node,ArrayList<Integer> cur_path){
// 叶子节点更新答案
if(cur_path.size()>ans){
return;
}
if(map[cur_node].size()==0 && cur_path.size()!=0 && cur_path.size()<ans){
ans=Math.min(ans, cur_path.size());
path=new ArrayList<>(cur_path);
return;
}
// 递归搜索
for(int i=0;i<map[cur_node].size();i++){
int next_node=map[cur_node].get(i);
if(arrive[next_node]){
cur_path.add(next_node);
dfs(next_node,cur_path);
cur_path.remove(cur_path.size()-1);
}
}
}
}
# Go
package main
import (
"bufio"
"fmt"
"os"
"sort"
)
var (
edges [][]int
blocks []int
used []bool
path []int
tmp int
res []int
judge bool
)
// dfs
func dfs(idx int, num int) {
// 到叶子节点，更新答案
if len(edges[idx]) == 0 {
if num < tmp {
tmp = num
res = append([]int(nil), path...) // slice复制
}
judge = true
}
//对同一层进行排序。这样保证了最先遇到的最短的答案也是字典序最小的
sort.Ints(edges[idx])
for _, a := range edges[idx] {
if blocks[a] == 0 && !used[a] {
used[a] = true
path = append(path, a)
dfs(a, num+1)
path = path[:len(path)-1]
used[a] = false
}
}
}
func main() {
in := bufio.NewReader(os.Stdin)
var n, m , k int
fmt.Fscan(in, &n)
fmt.Fscan(in, &m)
edges = make([][]int, n+1)
for i := 0; i < m; i++ {
var a, b int
fmt.Fscan(in, &a, &b)
edges[a] = append(edges[a], b)
}
fmt.Fscan(in, &k)
blocks = make([]int, n+1)
for i := 0; i < k; i++ {
var k1 int
fmt.Fscan(in, &k1)
blocks[k1] = 1
}
used = make([]bool, n+1)
path = []int{0}
used[0] = true
tmp = 0x7fffffff
dfs(0, 1)
if judge {
for i := 0; i < len(res); i++ {
fmt.Printf("%d", res[i])
if i != len(res)-1 {
fmt.Printf("->")
}
}
} else {
fmt.Println("NULL")
}
}
# Js
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function () {
// 结点总数 例如 4个节点 即 0 - 3
let nodeTotal = Number(await readline())
// 0 - 3 头节点
let edges = new Array(nodeTotal)
for(let i = 0; i < nodeTotal ; i++){
edges[i] = []
}
// 这边先读取变，然后 sort一下
// 前者小的在前 ，后者在前面的基础上 也小的在前
let edgeNum = Number(await readline())
let edgeArr = []
for(let i = 0; i < edgeNum; i++)
edgeArr.push((await readline()).split(" ").map(Number))
// sort
edgeArr.sort((a, b) => {
if (a[0] === b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
});
for(let i = 0; i < edgeNum; i++){
let [beginNode, endNode] = edgeArr[i]
edges[beginNode].push(endNode)
}
// 有几条边 例如 3条
// 禁止的节点个数
let forbiddenNum = Number(await readline())
// let forbiddenNodes = []
let forbiddenNodes = new Array(nodeTotal).fill(true)
// 这些点被禁用 存储一下
for(let j = 0; j < forbiddenNum; j++)
forbiddenNodes[Number(await readline())] = false
let temp = []
let minLen = Infinity
let result = ""
function dfs(currNode){
temp.push(currNode)
let useEdge = edges[currNode]
let useEdgeFilter = useEdge.filter( node => forbiddenNodes[node])
// 叶子节点更新答案
if(useEdge.length == 0){
if(minLen > temp.length){
minLen = temp.length
result = temp.join("->")
}
return;
}
// 递归搜索
for(let i = 0; i < useEdgeFilter.length; i++){
dfs(useEdgeFilter[i])
temp.pop()
}
}
dfs(0)
if(minLen == Infinity)
console.log("NULL")
else
console.log(result)
}()
// by kaikaichaoren2
← 第1题-塔子哥监考 第1题-引擎模块初始化 →