#include <iostream>
#include <vector>
#include <stack>

using namespace std;

/*
 输入
 6
 9
 0 1 2
 0 2 3
 1 2 2
 1 3 4
 2 3 1
 2 4 3
 3 4 2
 3 5 7
 4 5 4
 */
int main(int argc, const char * argv[]) {
    // 一共有多少个顶点
    int n;
    cin >> n;
    
    // 初始化这个“图”
    int64_t * graph = new int64_t[n * n];
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            graph[row * n + col] = INT64_MAX;
        }
    }
    
    // 一共有多少组边
    int p;
    cin >> p;
    for (int i = 0; i < p; i++) {
        // 依次输入每一条边
        int start, end, distance;
        cin >> start >> end >> distance;
        // 假设我们是无向图
        // 无向图具有对称性～
        graph[start * n + end] = distance;
        graph[end * n + start] = distance;
    }
    
    // 保存定点是否被访问过
    vector<bool> visited;
    visited.resize(n);
    
    // 保存源点到各点的最短距离
    vector<int64_t> distance;
    distance.resize(n);
    // 起始点到自己的距离是0～
    distance[0] = 0;
    // 其余各点都是正无穷
    for (int i = 1; i < n; i++) {
        distance[i] = INT64_MAX;
    }
    
    // 保存路径的数组
    vector<int> path;
    path.resize(n);
    
    // 从源点开始吧/
    int current = 0;
    while (true) {
        // 标记当前节点已经访问
        visited[current] = true;
        // 找出当前点可以一步访问到的所有的点
        for (int i = 0; i < n; i++) {
            if (visited[i] == false && // i 没有被访问过
                graph[current * n + i] != INT64_MAX // 并且current可以走到i这个顶点
                ) {
                // 从 0 ->...-> current -> i
                int64_t access_i_via_current = distance[current] + graph[current * n + i];
                // 从 0 ->...-> i
                int64_t access_i_via_other_path = distance[i];
                
                // 如果经过当前的点
                // 可以使得到 i 的距离变短的话
                if (access_i_via_current < access_i_via_other_path) {
                    // 那么更新路径～下面这个赋值的意思是
                    // 下标 i 这个点
                    // 应该从 current 来更近
                    path[i] = current;
                    // 更新距离
                    distance[i] = access_i_via_current;
                }
            }
        }
        
        int64_t new_minimum = INT64_MAX;
        for (int i = 0; i < n; i++) {
            // 从还没有访问过的点中
            if (visited[i] == false) {
                // 找出有着最小距离的点扩展
                if (distance[i] < new_minimum) {
                    current = i;
                    new_minimum = distance[i];
                }
            }
        }
        
        // 如果所有的点都访问过了
        // 那么这个 new_minimum 就还是初始值 +INF
        if (new_minimum == INT64_MAX) {
            // 此时就说明可以结束了
            break;
        }
    }
    
    cout << "minimum distance 0->" << n-1 << " is " << distance[n - 1] << '\n';
    
    // 保存最短路的路径
    stack<int> minimum_path;
    // 从最后一个点往回看
    current = n - 1;
    minimum_path.push(current);
    while (minimum_path.top() != 0) {
        // 从某个点到 current 是最近的
        // 把那个点放进去～
        minimum_path.push(path[current]);
        // 再来准备看是哪个点 到 那个点最近
        current = path[current];
    }
    
    // 按顺序输出整条路径
    while (!minimum_path.empty()) {
        cout << minimum_path.top() << ", ";
        minimum_path.pop();
    }
    cout << endl;
}

简单来说就是在每次尝试第 i 行新的摆法、并且递归的 trying 了它的下一行之后，需要还原第 i 行的状态。输出棋盘则可以直接在每次判断是可行解之后w

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode * rebin(vector<int> pre, vector<int> in) {
    // 首先看看有米有东西吧
    // 一个元素都没有的话
    // 这个二叉树就只有一个NULL节点
    // 直接返回即可w
    if (pre.size() == 0) return nullptr;
    
    // 根据前序遍历的定义 根节点一定在前序遍历结果的第一个位置上
    // 而中序遍历的话 根结点必然需要等到它的左子树都输出完才会出现
    // 利用这一点我们分开左右子树
    int root_value = pre[0];
    TreeNode * root = new TreeNode(root_value);
    // 找到根节点在中序遍历里的下标
    // 以此分开左右子树
    int root_index_of_in = 0;
    for (int i = 0; i < in.size(); i++) {
        if (in[i] == root_value) {
            root_index_of_in = i;
            break;
        }
    }
    // 分开左右子树
    // 按原始的顺序分别保存左右子树的前序遍历和中序遍历
    vector<int> left_pre, left_in, right_pre, right_in;
    // 先是左子树
    for (int i = 0; i < root_index_of_in; i++) {
        // 这里需要+1
        // 因为前序遍历的话 第一个元素是根节点
        // 所以需要跳过当前（下标为0）的这个元素
        left_pre.emplace_back(pre[i+1]);
        left_in.emplace_back(in[i]);
    }
    // 然后是右子树
    for (int i = root_index_of_in + 1; i < in.size(); i++) {
        right_pre.emplace_back(pre[i]);
        right_in.emplace_back(in[i]);
    }
    // 既然左右子树的前序遍历和中序遍历都有了
    // 和我们一开始拿到的初始条件很相似吧～
    // 那么递归吧w
    root->left = rebin(left_pre, left_in);
    root->right = rebin(right_pre, right_in);
    return root;
}

// 三种遍历方式～/
typedef enum {
    PRE_ORDER,
    IN_ORDER,
    POST_ORDER,
} TreeTraversal;

void print_with_order(TreeNode * root, TreeTraversal order) {
    // 如果根节点是空的
    // 那啥都不用说直接返回吧
    if (root == nullptr) return;
    
    // 看看使用什么序来遍历
    // 本质上仅仅只是输出当前root节点的位置不一样
    if (order == PRE_ORDER) {
        cout << root->val << ' ';
        print_with_order(root->left, order);
        print_with_order(root->right, order);
    } else if (order == IN_ORDER) {
        print_with_order(root->left, order);
        cout << root->val << ' ';
        print_with_order(root->right, order);
    } else {
        print_with_order(root->left, order);
        print_with_order(root->right, order);
        cout << root->val << ' ';
    }
}

int main(int argc, const char * argv[]) {
    vector<int> pre = {1,2,4,7,3,5,6,8};
    vector<int> in = {4,7,2,1,5,3,8,6};
    TreeNode * head = rebin(pre, in);
    
    // 用构建好的树输出前序和中序遍历来验证～
    cout << "pre: ";
    print_with_order(head, PRE_ORDER);
    cout << endl;
    
    cout << "in: ";
    print_with_order(head, IN_ORDER);
    cout << endl;
}