输出根到叶子的最短路径（答案不唯一则输出字典序最小的）

题目

输入n，表示有n个节点，然后输入m，表示有m条边，然后输入m行的(a,b)，表示从a号节点到b号节点有一条有向边，然后输入b，表示有b个节点是不可通行状态，然后输入b行的x，表示x号节点不可通行。

假设开局在根节点的位置，根节点就是0号节点。然后需要从根节点出发到叶子结点，要求输出路径。比如说0号节点依次通过1、4、5，发现5号节点就是叶子结点，那么就输出"0->1->4->5"。要求输出的路径是最短的那条，如果有多条最短路径，那么就输出字典序最小的路径。如果不存在一条路径从根节点到叶子结点，就输出"NULL"。

样例1：

4
3
0 1
0 2
0 3
2
2
3

0->1

样例2：

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

输出：

0->1->2

题目来源：http://codefun2000.com/p/P1196

解法一（双vector+bfs）

用vector<vector<int>> 存储这个树，用bfs，在遍历之前先排序，以保证第一个检索到的路径不仅是最短路，还是字典序最小的。部分编译器要求写作vector<vector<int> > ，即右尖括号之间需要添加空格。

基操补充：用vector定义二维数组

vector<vector<int>> g(N, vector<int>());如果写成这样的话，表示N个一维动态数组。
vector<vector<int>> g(N, vector<int>(M));如果写成这样的话，表示N行M列的二维数组

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>using namespace std;const int N = 10010;
vector<vector<int>> g(N, vector<int>());
int is_not_leaf[N];
int pred[N];
int n, m, d;
int a, b;
int block[N];
queue<int> q;void print_path(int start, int end) {if (start == end) cout << end;else {print_path(start, pred[end]);cout << "->" << end;}
}int main() {cin >> n >> m;for (int i = 0; i < m; i ++ ) {cin >> a >> b;is_not_leaf[a] = 1;g[a].push_back(b);}cin >> d;while (d -- ) {int x;cin >> x;block[x] = 1;}for (int i = 0; i < n; i ++ ) {sort(g[i].begin(), g[i].end());}q.push(0);while (q.size()) {int t = q.front();q.pop();for (int i = 0; i < g[t].size(); i ++ ) {int j = g[t][i];if (!block[j]) {q.push(j);pred[j] = t;if (!is_not_leaf[j]) {print_path(0, j);return 0;}}}}puts("NULL");return 0;
}

解法二（邻接表+bfs）

用邻接表的方式

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>using namespace std;queue<int> q;   // 用于bfs的队列
const int N = 10010;
int n, m, d;
int is_not_leaf[N];     // 初始化全0，表示所有点的初始状态都是叶子
int pred[N];    // 表示节点在最短路中的上一个节点
int h[N], e[N], ne[N], idx; // 用邻接表存储树
int block[N];   // 存储每个节点是否有障碍void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}void print_path(int st, int ed) {if (st == ed) cout << ed;else {print_path(st, pred[ed]);cout << "->" << ed;}
}int main() {memset(h, -1, sizeof h);cin >> n >> m;for (int i = 0; i < m; i ++ ) {int a, b;cin >> a >> b;add(a, b);is_not_leaf[a] = 1;}cin >> d;while (d -- ) {int x;cin >> x;block[x] = 1;}q.push(0);  // 根节点入队while (q.size()) {int t = q.front();q.pop();// 遍历t的所有下一个点，注意需要由小到大遍历vector<int> temp;for (int i = h[t]; i != -1; i = ne[i]) {// 先取出所有t的所有下一个节点int j = e[i];temp.push_back(j);}// 此时temp中有t的所有下一个节点sort(temp.begin(), temp.end());for (int i = 0; i < temp.size(); i ++ ) {int u = temp[i];if (!block[u]) {q.push(u);pred[u] = t;if (is_not_leaf[u] == 0) {print_path(0, u);return 0;}}}}// 如果程序运行到了这里，说明找不到达叶子的路径puts("NULL");return 0;
}

或者把bfs不要写在main中：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>using namespace std;queue<int> q;   // 用于bfs的队列
const int N = 10010;
int n, m, d;
int is_not_leaf[N];     // 初始化全0，表示所有点的初始状态都是叶子
int pred[N];    // 表示节点在最短路中的上一个节点
int h[N], e[N], ne[N], idx; // 用邻接表存储树
int block[N];   // 存储每个节点是否有障碍void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}void print_path(int st, int ed) {if (st == ed) cout << ed;else {print_path(st, pred[ed]);cout << "->" << ed;}
}// 从start开始遍历，抵达了叶子结点为止，并输出到达的叶子节点，如果无法到达叶子节点，则返回-1
int bfs(int start) {q.push(start);  // 根节点入队while (q.size()) {int t = q.front();q.pop();// 遍历t的所有下一个点，注意需要由小到大遍历vector<int> temp;for (int i = h[t]; i != -1; i = ne[i]) {// 先取出所有t的所有下一个节点int j = e[i];temp.push_back(j);}// 此时temp中有t的所有下一个节点sort(temp.begin(), temp.end());for (int i = 0; i < temp.size(); i ++ ) {int u = temp[i];if (!block[u]) {q.push(u);pred[u] = t;if (is_not_leaf[u] == 0) {return u;   // u是最短路径的叶子结点，并且字典序一定最小，则返回u}}}}return -1;  // 根节点不存在到达叶子结点的路径，返回-1
}int main() {memset(h, -1, sizeof h);cin >> n >> m;for (int i = 0; i < m; i ++ ) {int a, b;cin >> a >> b;add(a, b);is_not_leaf[a] = 1;}cin >> d;while (d -- ) {int x;cin >> x;block[x] = 1;}int ed = bfs(0);if (ed != -1) print_path(0, ed);else// 如果程序运行到了这里，说明找不到达叶子的路径puts("NULL");return 0;
}

解法三（邻接表+dfs）

稍微和bfs的写法不太一样，可以好好体会

当dfs(u) 的时候，需要dfs(u的所有下一个节点)，并且因为题目有字典序的要求，所以需要从小到大依次遍历u的所有下一个节点。遍历的过程中如果遇到叶子节点，就将leaf和dist[leaf]（假设叶子节点编号为leaf）存到数组中。最后在数组中找到dist最小的leaf，如果dist一样就用先找到的leaf作为终点（输出路径的函数需要用到终点的编号）。

对于将leaf和dist[leaf]存到数组中，这里稍微有些坑：
⚠️我原本想用priority_queue，即heap存储{dist[leaf], leaf}，这样输出结果的时候只需要取用heap.top()即可。但是这样想是错误的，原因写在注释里了——会破坏字典序，当dist相同的时候，leaf越小越靠近堆顶，可能heap.top()只是代表叶子结点的编号最小，但是不是路径的字典序最小

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>using namespace std;const int N = 10010;
int h[N], e[N], ne[N], idx;
int is_not_leaf[N], block[N], pred[N];
int n, m, d;
int a, b;
typedef pair<int, int> PII;
// 本意是将所有到达的叶子节点和对应的到达叶子节点的距离放进heap，即heap.push({dist[leaf], leaf})
// 然后可以根据dist排序，但是这样会有一个问题，这是个pair，如果dist一样，那么就会按照leaf的大小排序，可能会破坏字典序
// priority_queue<PII, vector<PII>, greater<PII>> heap;
vector<PII> res;
int dist[N];    // 存放根节点到各个节点的最短路径void add(int a, int b) {e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}void print_path(int start, int end) {if (start == end) cout << end;else {print_path(start, pred[end]);cout << "->" << end;}
}// 从start开始遍历，遇到叶子结点则记录到达叶子节点的路径长度
void dfs(int start) {if (block[start]) return;    // 如果start有障碍物，说明无法从start出发到达叶子结点if (is_not_leaf[start] == 0) {// 如果start这节点就是叶子节点，就将它加入heapres.push_back({dist[start], start});return;}// 由小到大依次遍历start节点的所有下一个节点vector<int> temp;   // 用与存储start节点的所有下一个节点，并且用它来给这些节点排序for (int i = h[start]; i != -1; i = ne[i]) {int j = e[i];temp.push_back(j);}sort(temp.begin(), temp.end());for (int i = 0; i < temp.size(); i ++ ){int u = temp[i];    // 当前需要遍历的节点是uif (block[u] == 0) {// 如果节点u没有障碍，才去遍历u// 由于这是一棵树，所以不存在对一个节点的重复遍历，所以不需要记录已访问的节点pred[u] = start;dist[u] = dist[start] + 1;dfs(u);   // 存储对u的遍历结果}}
}int main() {memset(h, -1, sizeof h);cin >> n >> m;while (m -- ) {cin >> a >> b;add(a, b);is_not_leaf[a] = 1;}cin >> b;while (b -- ) {int x;cin >> x;block[x] = 1;}dfs(0);if (res.size()) {int leaf;int temp_max = 0x3f3f3f3f, temp_leaf;for (auto t : res) {int d = t.first, u = t.second;if (d < temp_max) {temp_leaf = u;temp_max = d;}}print_path(0, temp_leaf);}else puts("NULL");return 0;
}