题意分析

我们需要摧毁一些公交车站，使得从 $1$ 号车站到 $n$ 号车站的最短路径长度大于 $k$。摧毁一个车站会同时摧毁所有与之相连的道路（包括进入和离开的道路）。目标是找到需要摧毁的最少车站数量。

解题思路

1. 问题转化：摧毁车站使得从起点1到终点n的最短路径>k分钟。转化为最小点割问题——找到最少需要删除的点，使新图中最短路径>k。

2. 核心方法： BFS：快速计算当前图的最短路径（边权为1，适合BFS） DFS+剪枝：尝试删除每个非关键点（非1/n点），保留最小删除数

3. 关键优化： 当删除点数≥当前最优解时立即剪枝 优先处理更可能构成最短路径的点

C++代码

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

using namespace std;

const int MAXN = 55;
const int INF = 1e9;

int n, m, k;
vector<int> adj[MAXN];
bool bad[MAXN];
int ans;

bool bfs() {
    vector<int> dis(n + 1, INF);
    queue<int> q;
    dis[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (size_t i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i];
            if (!bad[v] && dis[v] == INF) {
                dis[v] = dis[u] + 1;
                if (v == n) break;
                q.push(v);
            }
        }
    }
    return dis[n] > k;
}

void dfs(int u, int cnt) {
    if (cnt >= ans) return;
    if (bfs()) {
        ans = min(ans, cnt);
        return;
    }
    if (u > n) return;
    if (u == 1 || u == n) {
        dfs(u + 1, cnt);
        return;
    }
    bad[u] = true;
    dfs(u + 1, cnt + 1);
    bad[u] = false;
    dfs(u + 1, cnt);
}

int main() {
    while (true) {
        cin >> n >> m >> k;
        if (n == 0 && m == 0 && k == 0) break;
        for (int i = 1; i <= n; ++i) {
            adj[i].clear();
        }
        for (int i = 0; i < m; ++i) {
            int s, f;
            cin >> s >> f;
            adj[s].push_back(f);
        }
        memset(bad, false, sizeof(bad));
        ans = INF;
        dfs(1, 0);
        cout << ans << endl;
    }
    return 0;
}