P3547 [POI2013] CEN-Price List 题解

Description

给定一个 $n$ 个点 $m$ 条边的无向图，边权均为 $a$。

现在将原来图中满足最短路等于 $2a$ 所有的点对 $(x,y)$ 之间加一条长度为 $b$ 的无向边。

给定 $k$，求点 $k$ 到所有点的最短路是多少。

$1\leq n,m\leq 10^5$。

Solution

首先有个显然的结论是对于所有加边前 $k\to i$ 的最短路 $p_1(k)\to p_2\to\dots\to p_{m}(1)$，对于 $\forall 1\leq i\leq m-2$，一定满足 $p_i$ 和 $p_{i+2}$ 没有连边，否则最短路一定会更短。

那么加边之后的最短路就只有三种了：全 $a$；前面一堆 $a$ 加 $0/1$ 个 $b$；全 $b$。

对于前两种情况可以直接在原图上跑 bfs 求出。

考虑怎么做全 $b$ 的情况。

有一种暴力也是 bfs，每次转移就暴力枚举所有 $u\to v\to w$，满足 $(u,w)$ 没有边然后让 $dis_w\leftarrow dis_u+1$。

但是这样做是 $O(m^2)$ 的。

注意到对于一个转移 $u\to v\to w$ 如果 $(u,w)$ 没有边，那么这次转移后 $(v,w)$ 这条边就再也无法作为转移的第二条边进行成功的转移，可以直接删掉。

然后会发现如果 $u,v,w$ 不构成三元环则每次枚举必然会删掉至少一条边。如果构成三元环，由于三元环个数是 $O(m\sqrt m)$ 级别的，而每个三元环只会遍历 $O(1)$ 次，所以复杂度是 $O(m\sqrt m)$ 的。

时间复杂度：$O(m\sqrt m)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e5 + 5;

int n, m, s, A, B;
int ans[kMaxN];
std::vector<int> G[kMaxN], _G[kMaxN];

void del(std::vector<int> &vec, int p) {
  std::swap(vec[p], vec[(int)vec.size() - 1]);
  vec.pop_back();
}

void bfs1() {
  static int dis[kMaxN];
  static bool vis[kMaxN];
  std::queue<int> q;
  q.emplace(s), dis[s] = 0, vis[s] = 1;
  for (; !q.empty();) {
    int u = q.front(); q.pop();
    for (auto v : G[u]) {
      if (!vis[v]) {
        dis[v] = dis[u] + 1, vis[v] = 1, q.emplace(v);
      }
    }
  }
  for (int i = 1; i <= n; ++i)
    ans[i] = std::min(dis[i] * A, (dis[i] / 2) * B + (dis[i] % 2) * A);
}

void bfs2() {
  static int dis[kMaxN];
  static bool vis[kMaxN], have[kMaxN];
  std::queue<int> q;
  q.emplace(s), dis[s] = 0, vis[s] = 1;
  for (; !q.empty();) {
    int u = q.front(); q.pop();
    for (auto v : G[u]) have[v] = 1;
    for (auto v : G[u]) {
      std::vector<int> vec;
      for (int i = 0; i < (int)_G[v].size(); ++i) {
        int w = _G[v][i];
        if (w != u && !have[w]) {
          if (!vis[w]) dis[w] = dis[u] + 1, vis[w] = 1, q.emplace(w);
          vec.emplace_back(i);
        }
      }
      for (auto p : vec) {
        del(_G[v], p);
      }
    }
    for (auto v : G[u]) have[v] = 0;
  }
  for (int i = 1; i <= n; ++i)
    if (vis[i])
      ans[i] = std::min(ans[i], dis[i] * B);
}

void dickdreamer() {
  std::cin >> n >> m >> s >> A >> B;
  for (int i = 1; i <= m; ++i) {
    int u, v;
    std::cin >> u >> v;
    G[u].emplace_back(v), G[v].emplace_back(u);
    _G[u].emplace_back(v), _G[v].emplace_back(u);
  }
  memset(ans, 0x3f, sizeof(ans));
  bfs1(), bfs2();
  for (int i = 1; i <= n; ++i) std::cout << ans[i] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}