题解：P1811 最短路

· · 题解

题目分析

没想到什么好思路，随便胡了个迭代加深搜索上去。

IDDFS 具体过程（代码角度）：

初始化一个变量 dep 表示当前允许搜的深度（也就是最多走多少步），从 dep = 1 开始（或者从 0 开始但第一次 dfs 传的是深度 1），进入一个循环，每次循环都设置 vis 和 path 的初始状态，调用 dfs(1, 0, 1)，也就是从节点 1 开始搜，父节点是 0（虚拟的），当前深度是 1。

在 dfs 函数里，先判断当前深度 d 是否超过当前限制的 dep，超过就直接返回；如果当前节点 x 就是 n，说明找到了一个路径，如果这个路径的步数 d 比之前找到的更短，就更新最短步数 ans 和路径数组 ans2。

接着遍历当前节点 x 的所有相邻节点 y，如果这条边 x→y 已经走过（用 vis_{x,y} 判断）或者这条边是被限制的连续边（用 p_{fa,x} = y 判断），就跳过；否则就标记 vis_{x,y} 为已走，把 y 记录到 path_d，然后递归调用 dfs(y, x, d + 1) 去搜下一层，搜完之后回溯，把 vis_{x,y} 恢复，path_d 清空。

如果在某次循环中 dfs 找到了终点 n（也就是 ans 被更新了），就跳出循环；如果没找到，就把 dep 加 1，继续下一轮更深一层的搜索。

当最终找到最短路径后，输出 ans - 1（因为 ans 是节点数，边数等于节点数减 1），然后按照 path 数组里记录的节点顺序，输出从起点到终点的路径 ans2。

代码

#include <bits/stdc++.h>
using namespace std;
int n, m, k, p[3005][3005], dep, vis[3005][3005], ans = 0x3f3f3f3f;
int path[30005], ans2[30005]; 
vector <int> edge[30005];
inline void dfs (int x, int fa, int d) {
    if (d > dep) return;
    if (x == n) {
        if (ans > d) {
            ans = d;
            memcpy (ans2, path, sizeof (path));
        }
        return ;
    }
    for (auto y : edge[x]) {
        if (vis[x][y] || p[fa][x] == y) continue;
        vis[x][y] = 1;
        path[d] = y;
        dfs (y, x, d + 1);
        path[d] = 0;
        vis[x][y] = 0;
    }
}
int main () {
    scanf ("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int a, b;
        scanf ("%d%d", &a, &b);
        edge[a].push_back (b);
        edge[b].push_back (a);
    }
    for (int i = 1; i <= k; i++) {
        int x, y, z;
        scanf ("%d%d%d", &x, &y, &z);
        p[x][y] = z;
    }
    while (-1) {
        vis[0][1] = 1;
        path[0] = 1;
        dfs (1, 0, 1);
        if (ans != 0x3f3f3f3f) break;
        dep++;
    }
    printf ("%d\n", ans - 1);
    for (int i = 0; i <= ans - 1; i++) printf ("%d ", ans2[i]);
    return 0;
}