#11WA,其他全对
查看原帖
#11WA,其他全对
1125575
lordrigs楼主2024/8/26 14:20
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
struct Node
{
    int id, st;
};
int n, m, s, t;
bool f[10005], g[10005];
vector <int> a[10005], b[10005];
queue <int> q;
queue <Node> q2;
int main()
{
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> s >> t;
        a[s].push_back(t);
        b[t].push_back(s);
    }
    cin >> s >> t;
    memset(f, 1, sizeof(f));
    q.push(t);
    f[t] = 0;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int i = 0; i < b[x].size(); i++)
            if (!g[b[x][i]])
            {
                f[b[x][i]] = 0;
                q.push(b[x][i]);
                g[b[x][i]] = 1;
            }
    }
    for (int i = 1; i <= n; i++)
    {
        f[0] = 0;
        for (int j = 0; j < a[i].size(); j++)
            if (f[a[i][j]])
            {
                f[0] = 1;
                break;
            }
        g[i] = f[0];
    }
    memset(f, 0, sizeof(f));
    q2.push({s, 0});
    while (!q2.empty())
    {
        Node x = q2.front();
        q2.pop();
        if (x.id == t)
        {
            cout << x.st;
            return 0;
        }
        for (int i = 0; i < a[x.id].size(); i++)
        {
            if (!g[a[x.id][i]] && !f[a[x.id][i]])
            {
                q2.push({a[x.id][i], x.st + 1});
                f[a[x.id][i]] = 1;
            }
        }
    }
    cout << -1;
    return 0;
}
2024/8/26 14:20
加载中...