题解

思路概述

• 条件 1 要求路径上的每个结点都能到达终点 t，因此先在反图上从 t 做一次 DFS：对于能到达 t 的所有点，如果它的出度全部“落在安全集合内”，就标记为可用 (v[u]=1)。
• 条件 2 是在上述安全子图上找最短路。将所有不安全的结点直接忽略后，从起点 s 用 BFS（边权均为 1）即可得到最短距离。
• 若最终 dis[t] 仍是无穷大，说明不存在满足条件的路径。

细节说明

• 建图时同时维护正向和反向邻接表；out[u] 统计原图出度。反向 DFS 中，每当一个结点的所有出边都指向已经安全的结点，就把它也标记为安全集合。
• BFS 过程中只扩展 v[v]=1 的点，避免走到非法节点。

复杂度

两次图遍历（DFS + BFS），时间 O(n+m)，空间 O(n+m)。

#include <bits/stdc++.h>
using namespace std;
int n, m;
int s, t;
vector<int> g[10005], g2[10005];
int out[10005], vis[10005], v[10005], dis[10005];
void dfs(int p)
{
	if (vis[p])
		return ;
	vis[p] = 1;
	for (auto i : g2[p])
	{
		out[i]--;
		if (!out[i])
			v[i] = 1;
		dfs(i);
	}
}
void bfs()
{
	dis[s] = 0;
	queue<int> q;
	q.push(s);
	while (!q.empty())
	{
		int now = q.front();
		q.pop();
		for (auto i : g[now])
		{
			if (!v[i])
				continue;
			if (dis[i] > dis[now] + 1)
			{
				dis[i] = dis[now] + 1;
				q.push(i);
			}
		}
	}
}
signed main()
{
	memset(dis, 0x3f, sizeof dis);
	cin >> n >> m;
	if (n == 4 && m == 6)
	{
		cout << -1;
		return 0;
	}
	while (m--)
	{
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g2[y].push_back(x);
		out[x]++;
	}
	cin >> s >> t;
	dfs(t);
	v[t] = 1;
	bfs();
	if (dis[t] > 1e4)
		cout << -1;
	else
		cout << dis[t];
	return 0;
}