信息传递

AcWing-517-信息传递

分析

见《进阶指南》第362页。

有向图的最小环问题。

实现

#include <iostream>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 200010;
struct edge {
    int to, next, w;
};
edge e[N];
int idx, head[N];
struct node {
    int idx, dis;
    bool operator < (const node& o) const {
        return dis > o.dis;
    }
};
int n;
int dis[N];
bool mark[N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
int dijkstra (int s) {
    memset(mark, 0, sizeof(mark));
    memset(dis, 0x3f, sizeof(dis));
    
    priority_queue<node> pq;
    dis[s] = 0;
    pq.push({ s, dis[s] });
    while (!pq.empty()) {
        int cur = pq.top().idx;
        pq.pop();
        if (cur == s && mark[cur] == true) return dis[cur];
        if (mark[cur] == true) continue;
        mark[cur] = true;
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to, w = e[i].w;
            if (dis[cur] + w < dis[to]) {
                dis[to] = dis[cur] + w;
                pq.push({ to, dis[to] });
            }
        }
        if (cur == s) dis[cur] = inf;
    }
    return inf;
}

int main () {
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1, to; i <= n; ++ i) {
        scanf("%d", &to);
        add_edge(i, to, 1);
    }

    int res = inf;
    for (int s = 1; s <= n; ++ s)
        res = min(res, dijkstra(s));
    printf("%d", res);
    return 0;
}