问题深度解析
核心规则梳理
问题本质：在有向图中寻找满足特殊约束的最短路径
关键约束条件：
路径上的所有点，其所有出边指向的点都必须能直接或间接到达终点t
在满足条件1的情况下，路径长度最短
终点t没有出边（题目保证）
解题思路推导
反向图构建：
为了高效判断哪些点能到达终点t，我们需要构建反向图（将所有边的方向反转）
在反向图中从t出发进行BFS/DFS，所有能到达的点即为原图中能到达t的点
合法点筛选：
对于原图中的每个点u，检查其所有出边指向的点是否都在能到达t的点集合中
满足条件的点u即为合法点，可以出现在路径中
最短路径计算：
在原图中只保留合法点之间的边，然后从s出发进行BFS计算到t的最短路径
完整可运行代码（带详细注释）
代码详细解释
关键变量说明
变量名 类型 作用
g vector[] 存储原图的邻接表
rg vector[] 存储反向图的邻接表
can_reach bool[] 标记原图中能到达t的点
valid bool[] 标记合法点（满足条件的点）
dist int[] 存储从s到各点的最短距离
核心逻辑详解
反向图BFS：
在反向图中从t出发进行BFS，所有能到达的点即为原图中能到达t的点
时间复杂度：O(n + m)
合法点筛选：
对于每个点u，检查其所有出边指向的点是否都能到达t
同时u本身必须能到达t，才是合法点
时间复杂度：O(n + m)
合法子图BFS求最短路径：
在只包含合法点的子图中，从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
