90分超时
查看原帖
90分超时
844496
J_Kobe楼主2024/3/30 08:52
#include <bits/stdc++.h>
using namespace std;

int n, m, s, t;
vector<int> a[10005];
bool flag2[10005], flag3;
bool f[10005], flag[10005]; // flag能否到达终点 
struct node{
	int u, v; // u那个点,v多久 
};
queue<node> q;
int bfs()
{
	f[s] = 1;
	q.push((node){s, 0});
	while (q.empty() == 0)
	{
		node k = q.front();
		q.pop();
		if (k.u == t)
		{
			return k.v;
		}
		bool ff = true;
		for (int i = 0; i < a[k.u].size(); i++)
		{
			if (flag[a[k.u][i]] == 0)
			{
				ff = false;
				break;
			}
		}
		if (ff == false)
		{
			continue;
		}
		for (int i = 0; i < a[k.u].size(); i++)
		{
			if (f[a[k.u][i]] == 0)
			{
				f[a[k.u][i]] = 1;
				q.push((node){a[k.u][i], k.v+1});
			}
		}
	}
	return -1;
}
bool dfs(int x, int k)
{
	if (x == t)
	{
		flag[k] = 1;
		return 1;
	}
	for (int i = 0; i < a[x].size(); i++)
	{
		if (flag2[a[x][i]] == 0)
		{
			flag2[a[x][i]] = 1;
			dfs(a[x][i], k);
		}
	}
	return 0;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie();cout.tie();
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		a[x].push_back(y);
	}
	cin >> s >> t;
	for (int i = 1; i <= n; i++)
	{
		if (flag[i] == 0)
		{
			flag2[i] = 1;
			dfs(i, i);
			memset(flag2, 0, sizeof(flag2));
		}
	}
	cout << bfs();
	return 0;
}
2024/3/30 08:52
加载中...