60分求调
查看原帖
60分求调
947380
jiangxinyang2012楼主2024/4/6 14:23
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;
vector<int> G[N], H[N];
struct Node {
    int u, w;
    bool operator<(const Node &rhs) const {
        return w < rhs.w;
    }
};
int dis[N];
bool vis[N];
bool check[N];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        if (u == v) {
            continue;
        }
        H[v].push_back(u);
        G[u].push_back(v);
    }
    int s, t;
    scanf("%d%d", &s, &t);
    priority_queue<Node> q;
    memset(dis, 0x3f, sizeof dis);
    q.push({t, dis[t] = 0});
    while (!q.empty()) {
        int u = q.top().u;
        q.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto v : H[u]) {
            if (dis[v] > dis[u] + 1) {
                q.push({v, dis[v] = dis[u] + 1});
            }
        }
    }
    if (dis[s] == INF) {
        printf("-1\n");
    } else {
        for (int u = 1; u <= n; u++) {
            check[u] = 1;
            for (auto v : G[u]) {
                if (dis[v] == INF) {
                    check[u] = 0;
                    break;
                }
            }
        }
        if (!check[s]) {
            printf("-1\n");
            return 0;
        }
        memset(dis, 0x3f, sizeof dis);
        memset(vis, 0, sizeof vis);
        q.push({s, dis[s] = 0});
        while (!q.empty()) {
            int u = q.top().u;
            q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (auto v : G[u]) {
                if (dis[v] > dis[u] + 1 && check[v]) {
                    q.push({v, dis[v] = dis[u] + 1});
                }
            }
        }
        if (dis[t] == INF) {
            printf("-1\n");
        } else {
            printf("%d\n", dis[t]);
        }
    }
    return 0;
}

2024/4/6 14:23
加载中...