CF-346 D. Robot Control(反向建图spfa)

题目链接

题意

有向图(有环)中有一个机器人,机器人有三种规则:

1. 重复访问同一个点会自我销毁
2. 无路可走会自我销毁
3. 多岔路口会随机选择

为了让机器人安全的从 S S S到 T T T,可以在多岔路口制定它的方向来避免情况1,2的发生,求最少需要指定方向几次

思路

有一个转移方程:

对于点 u u u和它所有的出边 v v v, d p [ u ] dp[u] dp[u]表示从 u u u点到 T T T最少需要指定方向的次数

d p [ u ] = m i n ( m i n ( d p [ v ] ) + 1 , m a x ( d p [ v ] ) ) dp[u] = min(min(dp[v]) + 1, max(dp[v])) dp[u]=min(min(dp[v])+1,max(dp[v]))

1. 反向建图,从终点 T T T出发
2. 第一次访问 v v v点 d p [ v ] = d p [ u ] + 1 dp[v] = dp[u] + 1 dp[v]=dp[u]+1, 将点v加到队尾最后更新其他点
3. 最后一次访问 v v v点 d p [ v ] = m i n ( d p [ v ] , d p [ u ] ) dp[v] = min(dp[v], dp[u]) dp[v]=min(dp[v],dp[u]), 将点v加到队首优先更新其他点

这题用 c i n cin cin很慢不知道为啥…(CF不是不卡读入吗?)

#include <bits/stdc++.h>
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
using namespace std;
int in[maxn], dp[maxn], vis[maxn];
vector<int> g[maxn];
void bfs(int s, int e) {
  fill(dp, dp+maxn, -1);
  fill(vis, vis+maxn, 0);
  deque<int> que;
  que.push_back(e);
  dp[e] = 0;
  while (!que.empty()) {
    int u = que.front();
    que.pop_front();
    if (vis[u]) continue;
    vis[u] = 1;
    if (u == s) return;
    for (auto v : g[u]) {
      in[v]--;
      if (in[v] == 0 && (dp[v] == -1 || dp[v] > dp[u])) {// 最后访问v点
        dp[v] = dp[u];
        que.push_front(v); // 优先更新下一个点
      }else if(dp[v] == -1) {// 第一次访问v点
        dp[v] = dp[u] + 1;
        que.push_back(v); // 最后更新下个点
      }
    }
  }
}
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  fill(in, in+maxn, 0);
  for (int i = 0; i < m; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    g[v].push_back(u);
    in[u]++;
  }
  int s, e;
  scanf("%d %d", &s, &e);
  bfs(s, e);
  printf("%d\n", dp[s]);
  return 0;
}