详细题解

问题深度解析
核心规则梳理
问题本质：在有向图中寻找满足特殊约束的最短路径

关键约束条件：

路径上的所有点，其所有出边指向的点都必须能直接或间接到达终点t
在满足条件1的情况下，路径长度最短
终点t没有出边（题目保证）
解题思路推导
反向图构建：

为了高效判断哪些点能到达终点t，我们需要构建反向图（将所有边的方向反转）
在反向图中从t出发进行BFS/DFS，所有能到达的点即为原图中能到达t的点
合法点筛选：

对于原图中的每个点u，检查其所有出边指向的点是否都在能到达t的点集合中
满足条件的点u即为合法点，可以出现在路径中
最短路径计算：

在原图中只保留合法点之间的边，然后从s出发进行BFS计算到t的最短路径

完整可运行代码（带详细注释）

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 10005;

vector<int> g[MAXN];       // 原图
vector<int> rg[MAXN];      // 反向图
bool can_reach[MAXN];      // 标记原图中能到达t的点
bool valid[MAXN];          // 标记合法点（满足条件的点）
int dist[MAXN];            // 存储最短距离

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);   // 原图添加边x->y
        rg[y].push_back(x);  // 反向图添加边y->x
    }
    
    int s, t;
    cin >> s >> t;
    
    // 第一步：在反向图中BFS，找出原图中能到达t的点
    memset(can_reach, 0, sizeof(can_reach));
    queue<int> q;
    q.push(t);
    can_reach[t] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : rg[u]) {  // 反向图中u的邻接点v，对应原图中v->u
            if (!can_reach[v]) {
                can_reach[v] = true;
                q.push(v);
            }
        }
    }
    
    // 如果起点s无法到达t，直接输出-1
    if (!can_reach[s]) {
        cout << -1 << endl;
        return 0;
    }
    
    // 第二步：筛选合法点
    memset(valid, 0, sizeof(valid));
    valid[t] = true;  // 终点t没有出边，肯定是合法点
    
    for (int u = 1; u <= n; ++u) {
        if (u == t) continue;
        
        bool is_valid = true;
        for (int v : g[u]) {  // 检查u的所有出边指向的点
            if (!can_reach[v]) {  // 如果有一个点不能到达t，则u不合法
                is_valid = false;
                break;
            }
        }
        
        if (is_valid && can_reach[u]) {  // 必须同时满足：u能到达t，且u的所有出边指向的点都能到达t
            valid[u] = true;
        }
    }
    
    // 如果起点s不是合法点，直接输出-1
    if (!valid[s]) {
        cout << -1 << endl;
        return 0;
    }
    
    // 第三步：在合法点构成的子图中BFS求最短路径
    memset(dist, -1, sizeof(dist));
    queue<int> q2;
    q2.push(s);
    dist[s] = 0;
    
    while (!q2.empty()) {
        int u = q2.front();
        q2.pop();
        
        if (u == t) break;  // 到达终点，提前退出
        
        for (int v : g[u]) {
            if (valid[v] && dist[v] == -1) {  // 只考虑合法点
                dist[v] = dist[u] + 1;
                q2.push(v);
            }
        }
    }
    
    cout << dist[t] << endl;
    
    return 0;
}

代码详细解释
关键变量说明
变量名 类型 作用
g vector[] 存储原图的邻接表
rg vector[] 存储反向图的邻接表
can_reach bool[] 标记原图中能到达t的点
valid bool[] 标记合法点（满足条件的点）
dist int[] 存储从s到各点的最短距离
核心逻辑详解
反向图BFS：

queue<int> q;
q.push(t);
can_reach[t] = true;

while (!q.empty()) {
    int u = q.front();
    q.pop();
    
    for (int v : rg[u]) {
        if (!can_reach[v]) {
            can_reach[v] = true;
            q.push(v);
        }
    }
}

在反向图中从t出发进行BFS，所有能到达的点即为原图中能到达t的点
时间复杂度：O(n + m)
合法点筛选：

for (int u = 1; u <= n; ++u) {
    if (u == t) continue;
    
    bool is_valid = true;
    for (int v : g[u]) {
        if (!can_reach[v]) {
            is_valid = false;
            break;
        }
    }
    
    if (is_valid && can_reach[u]) {
        valid[u] = true;
    }
}

对于每个点u，检查其所有出边指向的点是否都能到达t
同时u本身必须能到达t，才是合法点
时间复杂度：O(n + m)
合法子图BFS求最短路径：

memset(dist, -1, sizeof(dist));
queue<int> q2;
q2.push(s);
dist[s] = 0;

while (!q2.empty()) {
    int u = q2.front();
    q2.pop();
    
    if (u == t) break;
    
    for (int v : g[u]) {
        if (valid[v] && dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q2.push(v);
        }
    }
}

在只包含合法点的子图中，从s出发进行BFS求最短路径
时间复杂度：O(n + m)
输入输出示例验证
示例输入2：
6 6
1 2
1 3
2 6
2 5
4 5
3 4
1 5
反向图BFS后，能到达5的点是1,3,4,5
筛选合法点：
点1的出边指向2和3，其中2不能到达5，所以点1不合法？不，等一下，点1的出边指向2和3，其中2不能到达5，那点1是不是合法点？
不对，看题目说明，点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。但点1的出边指向2和3，其中2不能到达5，那点1是不是合法点？
哦，不对，题目条件是“路径上的所有点的出边所指向的点都直接或间接与终点连通”，也就是说，对于路径上的点u，u的所有出边指向的点都必须能到达t。
那点1的出边指向2和3，其中2不能到达5，那点1是不是合法点？但示例中的答案路径是1->3->4->5，这说明点1是合法点。
哦，我理解错了！题目条件是“路径上的所有点的出边所指向的点都直接或间接与终点连通”，这里的“出边所指向的点”是指路径上的点的出边所指向的点，还是指路径上的点的所有出边所指向的点？
再看题目描述：“路径上的所有点的出边所指向的点都直接或间接与终点连通。”
仔细看题目说明中的示例2：点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。这说明，对于路径上的点u，u的所有出边指向的点都必须能到达t，而不仅仅是路径上的边。
那为什么点1可以在路径中？点1的出边指向2和3，其中2不能到达5，那点1的出边所指向的点中有一个不能到达t，那点1是不是不合法？
哦，我看错了！示例2的输入中，点1的出边是1->2和1->3，点2的出边是2->6和2->5，点6不能到达5，但点2可以到达5（通过2->5）。那点2的出边所指向的点6不能到达5，那点2是不是不合法？
对，题目说明中说点2不能在答案路径中，因为点2连了一条边到点6，而点6不与终点5连通。这说明，只要点u有任何一个出边指向的点不能到达t，u就不能出现在路径中。
那点1的出边指向2和3，其中2是否是合法点？点2的出边指向6和5，其中6不能到达5，所以点2不合法，但点1的出边指向的点2是否能到达t？点2可以通过2->5到达t，所以点2是能到达t的，但点2本身不是合法点。
哦，我搞混淆了两个概念：
can_reach[u]：u能否到达t（原图中存在路径从u到t）
valid[u]：u是否是合法点（u能到达t，且u的所有出边指向的点都能到达t）
点2能到达t（通过2->5），所以can_reach[2] = true，但点2的出边指向6，而6不能到达t，所以valid[2] = false。
点1的出边指向2和3，其中2能到达t（can_reach[2] = true），3能到达t（can_reach[3] = true），所以点1的所有出边指向的点都能到达t，且点1本身能到达t，所以valid[1] = true。
哦，原来如此！我之前误解了合法点的条件，合法点的条件是：
u本身能到达t（can_reach[u] = true）
u的所有出边指向的点v，都能到达t（can_reach[v] = true）
而不是v必须是合法点！题目条件是“路径上的所有点的出边所指向的点都直接或间接与终点连通”，这里的“连通”是指能到达终点，而不是v必须是合法点。
我之前在代码中写的是对的，valid[u]的条件是is_valid && can_reach[u]，其中is_valid是检查u的所有出边指向的点v是否can_reach[v] = true，而不是valid[v] = true。
这样示例2中的点1是合法点，因为其所有出边指向的点2和3都能到达t（点2可以通过2->5到达t），虽然点2本身不是合法点，但这不影响点1的合法性。
而点2不是合法点，因为其出边指向的点6不能到达t，所以点2不能出现在路径中。
这样示例2的合法点是1,3,4,5，然后从1出发BFS到5的最短路径是1->3->4->5，长度为3，与示例一致。
复杂度分析
复杂度 分析
时间复杂度 O(n + m)
空间复杂度 O(n + m)
性能分析
对于n=10000，m=200000的情况，代码完全在时间限制内
使用邻接表存储图，空间效率高
BFS是线性时间复杂度，非常高效

边界测试用例
输入 输出 说明
3 2
1 2
2 1
1 3 -1 起点1无法到达终点3
4 4
1 2
2 3
3 4
1 3
1 4 2 合法路径是1->3->4（长度2），而1->2->3->4（长度3）不合法，因为点2的出边指向3（能到达4），但等一下，点2的出边只有指向3，3能到达4，所以点2是合法点？那最短路径应该是1->2->3->4（长度3）还是1->3->4（长度2）？哦，1->3->4更短，长度为2，所以输出2
2 1
1 2
1 2 1 起点1的出边指向2，2能到达2，所以1是合法点，最短路径长度为1
4 3
1 2
2 3
3 4
1 4 1 起点1的出边指向2和4，2能到达4，4能到达4，所以1是合法点，最短路径是1->4，长度为1