问题 : 摧毁巴士站
内存限制：128 MB
时间限制：1.000 S

题目描述
Gabiluso是最伟大的间谍之一。现在，他试图完成一个“不可能完成”的使命――减缓Colugu的军队到达机场的时间。Colugu有n个公共汽车站和m条道路。每条道路直接连接两个巴士站，所有的道路都是单向的。为了保持空气洁净，政府禁止所有军用车辆，因此，军队必须乘搭巴士去机场。两个巴士站之间，可能有超过一条道路。如果一个公共汽车站被破坏时，所有连接该站的道路将无法运作。Gabiluso需要做的是摧毁了一些公共汽车站，使军队无法在K分钟内到达机场。一辆公交车通过一条道路，都是一分钟。所有巴士站的编号从1到n。1号巴士站是在军营，第n号站是机场。军队始终从第一站出发。第一站和第n站不能被破坏，这里有大量的防御力量。当然也没有从第一站到第n站的道路。

请帮助Gabiluso来计算能完成使命所需摧毁的最低数目的巴士站。
输入
第一行包含三个整数n，m，k (2<n<=50,0<m<=4000,0<k<1000)。

接下来m行，每行2个整数s和f，表示从站s到站f有一条路。

输出
输出最少需要摧毁的巴士站数目。

样例输入
5 7 3
1 3
3 4
4 5
1 2
2 5
1 4
4 5
样例输出
2
提示
【数据规模】

30%的数据N<=15。

算法标签：DFS+迭代加深+BFS求最短路+网络流
思路：用DFS求删掉若干个点之后，检查最短路径是否>k，符合则答案加一.
在oj上提交用迭代加深跑了700多ms，直接dfs才60多ms，非常迷，也许是oj数据有点弱了
难点与关键在于用pre记录最短路径的所有节点，保证dfs只遍历最短路径上的节点.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
#include <cstring>

using namespace std;

int n, m, k; // n: 车站数量, m: 道路数量, k: 时间限制
vector<vector<int>> graph; // 图的邻接表表示
vector<bool> destroyed; // 存储当前被摧毁的车站状态
int ans = INT_MAX; // 最小需要摧毁的节点数
int pre[101]; // 前驱节点数组

// 使用BFS计算从起点到终点的最短路径长度
int bfs() {
    vector<int> dist(n + 1, INT_MAX); // 距离数组，初始化为无穷大
    queue<int> q; // BFS队列

    dist[1] = 0; // 起点到自身的距离为0
    q.push(1); // 将起点加入队列

    // BFS遍历
    while (!q.empty()) {
        int node = q.front(); // 当前节点
        q.pop();

        // 遍历当前节点的所有邻居
        for (int neighbor : graph[node]) {
            // 如果邻居没有被摧毁且未被访问过
            if (!destroyed[neighbor] && dist[neighbor] == INT_MAX) {
                dist[neighbor] = dist[node] + 1; // 更新邻居的距离
                pre[neighbor] = node; // 更新前驱节点
                q.push(neighbor); // 将邻居加入队列
            }
        }
    }



    return dist[n]; // 返回终点的最短距离
}

// 递归尝试删除节点并检查路径
void dfs(int dep) {
    if (dep > ans) return; // 如果当前删除节点数超过已知最优解，返回


    // 计算当前的最短路径长度
    int shortestPathLength = bfs();

    // 如果最短路径长度超过k，记录当前的删除节点数
    if (shortestPathLength > k) {
        ans = min(ans, dep); // 更新最小需要摧毁的节点数
        return;
    } else {
        vector<int> q; // 存储路径的节点
        q.push_back(n); // 终点

        // 回溯找到路径
        while (pre[q.back()] > 0) {
            q.push_back(pre[q.back()]); // 记录前驱节点
        }

        // 遍历路径中的节点（不包括起点和终点）
        for (int i = 1; i < q.size() - 1; ++i) { // 从1到倒数第二个节点
            int nodeToDelete = q[i];
            destroyed[nodeToDelete] = true; // 将当前节点标记为被摧毁
            dfs(dep + 1); // 递归调用，增加删除的节点数
            destroyed[nodeToDelete] = false; // 回溯，恢复当前节点的状态
        }
    }
}



int main() {
    cin >> n >> m >> k; // 输入车站数量、道路数量和时间限制
    graph.resize(n + 1); // 初始化图的邻接表
    destroyed.resize(n + 1, false); // 初始化destroyed状态

    // 输入道路信息
    for (int i = 0; i < m; ++i) {
        int s, f;
        cin >> s >> f;
        graph[s].push_back(f); // 添加从s到f的边
    }

    // 初始计算最短路径长度
    int initialShortestPathLength = bfs();
    if (initialShortestPathLength > k) {
        cout << 0 << endl; // 如果最短路径长度大于k，输出0并结束程序
        return 0;
    }


    dfs(0);
    cout << ans << endl; // 输出找到的最小摧毁数
    return 0;
}