自动搬运

查看原文

来自洛谷，原作者为

	xyf007 「（……哇～两人共乘耶。我正和男生两人共乘一辆自行车！咦、咦，怎么回事，这不是电视剧或电影情节对吧。讨、讨厌啦，早知道会这样，我一定会穿白色连身裙过来，唉～）」

搬运于2025-08-24 22:32:35，当前版本为作者最后更新于2021-07-25 13:26:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

出题人的官方题解

看到这道题可能会有一些错误的想法，典型的就是来回都走最短路，但实际上到一个点去时走最短路，回来则不一定。如下图：

1 号点是起点，8 号点是毒气点，可以到达的点为 1~6。

首先 BFS 求出每个点到起点和泄露点的距离。简单的想法是暴力枚举每一个点 BFS 看能否回到起点，复杂度 $O(n^2)$，可以拿到 30 分。

我们令 $t_x$ 表示能够回到起点到达 $x$ 点的最晚时间，那么起点相邻的点都是它们到毒气点的距离。对于其他的点 $u$ 有 $t_u=\max\limits_{(u,v) \in E}(t_v)-1$。
把所有起点相邻的点放进一个堆，用一个优先队列 BFS，每个点 $x$ 第一次被更新的时候就得到了 $t_x$，复杂度 $O(n \log n)$，可以获得 70 分。
然后你会发现 $t_x \leq n$，并且堆中 $t$ 的最大值单调不增，所以可以用一个 std::vector 来代替这个堆，复杂度 $O(n+m)$，可以通过此题。

#include <algorithm>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
struct Edge {
  int to, nxt;
} e[10000001];
int n, m, E, head[5000001], s, t, dis[5000001], h[5000001];
std::vector<int> q2[5000001];
bool vis[5000001];
class Queue {
 public:
  Queue() { head_ = tail_ = 0; }
  bool Empty() { return head_ == tail_; }
  void Clear() { head_ = tail_ = 0; }
  void Push(int x) { a_[tail_++] = x; }
  int Front() { return a_[head_]; }
  void Pop() { head_++; }
  ~Queue() {}

 private:
  int head_, tail_, a_[5000001];
} q;
char gc() {
  static char now[1 << 20], *S, *T;
  if (T == S) {
    T = (S = now) + std::fread(now, 1, 1 << 20, stdin);
    if (T == S) return EOF;
  }
  return *S++;
}
template <typename T>
void Read(T &x) {
  x = 0;
  char c = gc();
  while (c < '0' || c > '9') c = gc();
  x = c - '0';
  while ((c = gc()) >= '0' && c <= '9') x = x * 10 + c - '0';
}
template <typename T, typename... Args>
void Read(T &x, Args &... args) {
  Read(x);
  Read(args...);
}
void checkmax(int &x, int y) {
  if (x < y) x = y;
}
void checkmin(int &x, int y) {
  if (x > y) x = y;
}
void Add(int f, int t) {
  e[E].to = t;
  e[E].nxt = head[f];
  head[f] = E++;
}
int main(int argc, char const *argv[]) {
  std::memset(head, -1, sizeof(head));
  Read(n, m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    Read(u, v);
    Add(u, v);
    Add(v, u);
  }
  Read(s, t);
  std::memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  q.Push(s);
  vis[s] = true;
  while (!q.Empty()) {
    int u = q.Front();
    q.Pop();
    for (int i = head[u]; i != -1; i = e[i].nxt) {
      int v = e[i].to;
      if (vis[v]) continue;
      dis[v] = dis[u] + 1;
      q.Push(v);
      vis[v] = true;
    }
  }
  std::memset(h, 0x3f, sizeof(h));
  std::memset(vis, false, sizeof(vis));
  q.Clear();
  q.Push(t);
  h[t] = 0;
  vis[t] = true;
  while (!q.Empty()) {
    int u = q.Front();
    q.Pop();
    for (int i = head[u]; i != -1; i = e[i].nxt) {
      int v = e[i].to;
      if (vis[v] || v == s) continue;
      h[v] = h[u] + 1;
      q.Push(v);
      vis[v] = true;
    }
  }
  std::memset(vis, false, sizeof(vis));
  vis[s] = true;
  int max = 0;
  for (int i = head[s]; i != -1; i = e[i].nxt) {
    int v = e[i].to;
    if (h[v] > 5000000) continue;
    q2[h[v]].emplace_back(v);
    checkmax(max, h[v]);
    vis[v] = true;
  }
  for (int i = max; i >= 1; i--)
    for (auto &&u : q2[i])
      for (int j = head[u]; j != -1; j = e[j].nxt) {
        int v = e[j].to;
        if (vis[v]) continue;
        checkmin(h[v], h[u] - 1);
        vis[v] = true;
        q2[h[v]].emplace_back(v);
      }
  int ans = 0;
  for (int i = 1; i <= n; i++)
    ans += (vis[i] || h[i] == 0x3f3f3f3f) && (dis[i] < h[i]);
  std::cout << ans - 1;
  return 0;
}