题意

有一个 \(N\) 个点, \(M\) 条边的有向图, 初始有一个机器人在 \(1\) 号点. 每个时刻, 这个机器人会随机选择一条从该点出发地边并通过.当机器人到达点 \(N\) 时, 它就会自动关闭.

然而这个机器人如果在某个时刻到达自己曾经到过的点的话, 它就会爆炸. 因此, 你决定对机器人实施一些命令, 让它在某些时候按照规定的边走, 而非随机选择.

问对机器人最少使用多少条命令可以让它安全到达点 \(N\) .

\(N, M \le 10^6\)

题解

十分巧妙的一道好题～

首先可以无视掉 “不能到达曾经到过的点” 的限制, 因为最优答案一定不会存在这种情况.

因为到达曾经到过的点，你至少要付出更多代价才能回到这个点，所以绝对不优。

然后我们就可以考虑一个 \(dp\) 了，令 \(dp_u\) 为 \(u\) 走到 \(T\) 需要的最少命令。

那么显然有一个转移：

\[ dp_u=\min_{(u, v)} \{\min\{dp_v\}+1,\max\{dp_v\}\} \]

这个意义是很明显的，就不解释了。

这个本质上是个 \(0 / 1\) BFS 问题，用个双端队列维护就行了，\(0\) 加到队首， \(1\) 加到队尾就行了。

具体实现的时候，我们只有在第一次到达这个点的时候会更新 \(\min\{dp_v\}+1\) ，因为是 BFS 最早到的肯定是距离较小的点。

也就是队列中的点 \(dis\) 单调不下降。

然后最后一次到达这个点才会更新 \(\max\{dp_v\}\) ，同样这是 BFS 最晚到的点。

每个点我们只会访问一次，所以最后一次到达就是它入度减少到 \(0\) 的时候。

复杂度是 \(O(n + m)\) 的。

总结

对于一类图上有关 \(dp\) 的 \(\min,\max\) 问题能考虑 BFS 队列的 \(dis\) 单调不下降的性质来转移。

代码

记得要把边反向，以及入度也要反向。

#include 
    
     #define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)#define Set(a, v) memset(a, v, sizeof(a))#define Cpy(a, b) memcpy(a, b, sizeof(a))#define debug(x) cout << #x << ": " << x << endl#define DEBUG(...) fprintf(stderr, __VA_ARGS__)using namespace std;inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}inline int read() {    int x = 0, fh = 1; char ch = getchar();    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);    return x * fh;}void File() {#ifdef zjp_shadow    freopen ("D.in", "r", stdin);    freopen ("D.out", "w", stdout);#endif}const int N = 1e6 + 1e3;int n, m, deg[N], dp[N];vector
     
       G[N];int S, T; bitset
      
        vis;void Bfs() {    Set(dp, -1); deque
       
         Q; Q.push_front(T); dp[T] = 0;    while (!Q.empty()) {        int u = Q.front(); Q.pop_front();         if (u == S) return ;        if (vis[u]) continue ; vis[u] = true;        for (int v : G[u]) if (!-- deg[v]) {            if (!~dp[v] || dp[u] < dp[v]) dp[v] = dp[u], Q.push_front(v);        } else if (!~dp[v]) dp[v] = dp[u] + 1, Q.push_back(v);    }}int main () {    File();    n = read(); m = read();    For (i, 1, m) {        int u = read(), v = read();        G[v].push_back(u); ++ deg[u];    }    S = read(), T = read(); Bfs();    printf ("%d\n", dp[S]);    return 0;}