题解「JOI 2021 Final」ロボット / Robot

moongazer · 2021-03-01 16:05:44 · 题解

考虑从 u 到 v 的一条颜色为 c 长度为 w 的边，设 S_{u,c} 为以 u 为端点所有颜色为 c 的边的长度之和，要经过该边有两种策略：

将该边改为一种不冲突的颜色，费用 w。
将所有相同颜色的其他边改掉，费用 S_{u,c}-w。

发现 u 是菊花的中心且每条边的颜色两两不同的情况下 1 策略是不合法的，但是此时 2 策略费用为 0 故可以不考虑。

发现若有 u\to v，v\to x 两条边颜色都为 c 在 u\to v 选择 1 策略，v\to x 选择 2 策略那么改变 u\to v 边的颜色的代价会计算两边，考虑减去。

考虑建立虚点 v_c 由 u 向 v_c 连边权为 0 的边，v_c 向 x 连边权为 S_{v,c}-w 的边，发现这样 u\to v_c\to x 就是先 1 策略再 2 策略的代价。

于是跑 Dijkstra 即可。

最多每条边都建一个虚点，故点数是 \operatorname{O}(n+m) 的，边数还是 \operatorname{O}(m) 的，时间复杂度 \operatorname{O}((n+m)\log m)。

注意：以下参考代码大量使用 STL 和 C++17 特性，常数巨大且需要注意编译选项（亲测 std::map 比 std::unordered_map 快）。

const int N = 100005;

void addedge(int u, int v, int c, int w);

std::map<int, ll> sum[N], dis[N];
std::map<int, int> len[N], col[N];
std::map<int, std::vector<pii>> mp[N];

int n, m;

int main() {
  read(n), read(m);
  for (int i = 1; i <= m; ++i) {
    int u, v, c, w;
    read(u), read(v), read(c), read(w);
    addedge(u, v, c, w), addedge(v, u, c, w);
  }
  std::priority_queue<std::tuple<ll, int, int>> pq;
  auto upd = [&](int v, int c, ll udis) {
    if (!dis[v].count(c) || dis[v][c] > udis) {
      dis[v][c] = udis;
      pq.emplace(-udis, v, c);
    }
  };
  upd(1, 0, 0);
  while (!pq.empty()) {
    auto [d, u, c] = pq.top();
    d = -d;
    pq.pop();
    if (d != dis[u][c]) continue;
    for (auto [v, vc] : mp[u][c]) {
      ll w;
      if (c == vc)
        w = std::min(1ll * len[u][v], sum[u][col[u][v]] - len[u][v]);
      else if (c)
        w = sum[u][c] - len[u][v];
      else
        w = 0;
      upd(v, vc, d + w);
    }
  }
  if (dis[n].count(0))
    write(dis[n][0]), EL;
  else
    puts("-1");
  return 0;
}

void addedge(int u, int v, int c, int w) {
  col[u][v] = c, len[u][v] = w;
  sum[u][c] += w;
  mp[u][0].emplace_back(v, 0);
  mp[u][0].emplace_back(v, c);
  mp[u][c].emplace_back(v, 0);
}

题解 「JOI 2021 Final」ロボット / Robot

题解「JOI 2021 Final」ロボット / Robot