CF715B Complete The Graph 题解

Description

给 \(n\) 点 \(m\) 边的无向图，\(L\)，\(s\)，\(t\)。

修改 \(m\) 条边中边为 \(0\) 的边，使满足 \(s,t\) 的最短路长度是 \(L\)，且输出答案的时候边为 \(0\) 的边的权值必须在 \([1,10^{18}]\) 内。

Solution

考虑怎么判有无解。

容易发现将所有未知边边权设为 \(10^{18}\)，如果最短路小于 \(L\)，或者未知边设为 \(1\) 后最短路大于 \(L\) 时无解，否则有解。因为每次只将一条边的长度加 \(1\) 后最短路至多增加 \(1\)。

不妨设 \(dis_i\) 表示 \(i\) 在未知边边权为 \(1\) 时与 \(s\) 的距离，\(det\) 表示 \(L-dis_t\)。容易发现我们的任务就是让 \(dis_t\) 增加 \(det\)。

考虑再进行一次 dijkstra，如果当前松弛的边 \((u,v,w)\) 满足 \(dis_{v}+det>dis^{'}_{u}+w\) 且这条边未确定，就将 \(w\) 调整为 \(dis_{v}+det-dis^{'}_u\)，这样的话每个点的最短路一定不会增加超过 \(det\)，且 \(dis_t\) 一定能增加 \(det\)。

时间复杂度：\(O((n+m)\log n)\)。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 1e3 + 5, kMaxM = 1e4 + 5;

int n, m, L, s, t, det;
int u[kMaxM], v[kMaxM], w[kMaxM];
int dis1[kMaxN], dis2[kMaxN];
bool del[kMaxM];
std::vector<std::tuple<int, int, int>> G[kMaxN];

int dijkstra1(int *dis) {
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) G[i].clear();
  for (int i = 1; i <= m; ++i) {
    if (w[i]) {
      G[u[i]].emplace_back(v[i], w[i], i), G[v[i]].emplace_back(u[i], w[i], i);
    }
  }
  for (int i = 1; i <= n; ++i) {
    dis[i] = 1e18, vis[i] = 0;
  }
  std::priority_queue<std::pair<int, int>> q;
  q.emplace(0, s), dis[s] = 0;
  for (; !q.empty();) {
    int u = q.top().second; q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto [v, w, id] : G[u]) {
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.emplace(-dis[v], v);
      }
    }
  }
  return dis[t];
}

int dijkstra2(int *dis) {
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) G[i].clear();
  for (int i = 1; i <= m; ++i) {
    if (w[i]) {
      G[u[i]].emplace_back(v[i], w[i], i), G[v[i]].emplace_back(u[i], w[i], i);
    }
  }
  for (int i = 1; i <= n; ++i) {
    dis[i] = 1e18, vis[i] = 0;
  }
  std::priority_queue<std::pair<int, int>> q;
  q.emplace(0, s), dis[s] = 0;
  for (; !q.empty();) {
    int u = q.top().second; q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto [v, w, id] : G[u]) {
      if (del[id] && dis1[v] + det > dis[u] + ::w[id])
        ::w[id] = dis1[v] + det - dis[u];
      if (dis[v] > dis[u] + ::w[id]) {
        dis[v] = dis[u] + ::w[id];
        q.emplace(-dis[v], v);
      }
    }
  }
  return dis[t];
}

void print() {
  std::cout << "YES\n";
  for (int i = 1; i <= m; ++i)
    std::cout << u[i] - 1 << ' ' << v[i] - 1 << ' ' << w[i] << '\n';
}

void dickdreamer() {
  std::cin >> n >> m >> L >> s >> t;
  ++s, ++t;
  for (int i = 1; i <= m; ++i) {
    std::cin >> u[i] >> v[i] >> w[i];
    ++u[i], ++v[i];
    if (!w[i]) del[i] = 1, w[i] = 1e18;
  }
  int dis = dijkstra1(dis1);
  if (dis < L) return void(std::cout << "NO\n");
  if (dis == L) return print();
  for (int i = 1; i <= m; ++i)
    if (del[i])
      w[i] = 1;
  int now = dijkstra1(dis1);
  if (now > L) return void(std::cout << "NO\n");
  det = L - now;
  dijkstra2(dis2);
  print();
}

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;
}