LOJ #3490. 「JOISC 2021 Day2」逃跑路线

Description

在 IOI 王国，人们使用 Byou 作为时间单位。IOI 王国中的一天被分为了 $S$ 个时间单位。每天从最开始经过 $x\ (0 \le x < S)$ Byou 后的时间称为时刻 $x$。

IOI 王国由 $N$ 个城市组成，以 $0$ 到 $N-1$ 编号。其中有 $M$ 条双向道路连接某些城市，以 $0$ 到 $M-1$ 编号。你可以通过这些道路从一个城市到达另一个城市。第 $i\ (0 \le i \le M-1)$ 条道路连接城市 $A_i$ 和 $B_i$，且经过这条道路需要 $L_i$ Byou。

在每天，人们会在道路 $i$ 进行一次严格的安检，并从时刻 $C_i$ 持续到当天结束。

JOI 帮是 IOI 王国的一个秘密组织。由于其神秘性，JOI 帮的成员构成是高度机密。这意味着其中的成员不能遭遇任何一次安检。因此，如果 JOI 帮的成员需要经过道路 $i$，TA 从 $A_i$ 或 $B_i$ 起身出发的时刻 $x$ 必须满足 $0 \le x \le C_i - L_i$。由于安检并非在城市内进行，而是在路上，所以 JOI 帮的成员可以在道路 $i$ 安检时出现在城市 $A_i$ 或 $B_i$。

JOI 帮有 $Q$ 个成员，以 $0$ 到 $Q-1$ 编号。成员 $j\ (0 \le j \le Q-1)$ 会在某天的时刻 $T_j$ 从城市 $U_j$ 出发前往城市 $V_j$。成员们可以在途中的某个城市里小憩一会。成员 $j$ 可能需要很多天才能到达城市 $V_j$。

请您编写一个程序，对于给定的城市、道路、安检和 JOI 帮的成员的信息，对于每个 $j\ (0 \le j \le Q-1)$ 计算出成员 $j$ 从 $U_j$ 到达 $V_j$ 的最少时间。

• $2 \le N \le 90$。
• $N-1 \le M \le \frac{N(N-1)}2$。
• $2 \le S \le 10^{15}$。
• $1 \le Q \le 3\times 10^5$。
• $0 \le A_i \le N-1\ (0 \le i \le M-1)$。
• $0 \le B_i \le N-1\ (0 \le i \le M-1)$。
• $A_i \ne B_i\ (0 \le i \le M-1)$。
• $(A_i,B_i) \ne (A_k,B_k),(A_i,B_i) \ne (B_k,A_k)\ (0 \le i < k \le M-1)$。
• $1 \le L_i <S\ (0 \le i \le M-1)$。
• $L_i \le C_i <S\ (0 \le i \le M-1)$。
• 您可以通过城市之间的某些道路从任意城市到达任意其他城市。
• $0 \le U_j \le N-1\ (0 \le j \le Q-1)$。
• $0 \le V_j \le N-1\ (0 \le j \le Q-1)$。
• $U_j \ne V_j\ (0 \le j \le Q-1)$。
• $0 \le T_j < S\ (0 \le j \le Q-1)$。

Solution

首先有个单次询问 $O(n^2+m)$ 的做法是直接暴力跑 dijkstra 最短路。显然过不了。

考虑优化。

刚才那个做法主要慢在没有任何预处理而每次重新做询问，导致询问时间复杂度过高而超时。注意到当一个点第一次被道路卡后，时间$\bmod S$ 一定为 $0$，这样起点的状态只有 $O(n)$ 种，可以预处理了。

根据上面那个做法可以将答案路径分为两种：在一天内走完、走至少两天。

先考虑第一种情况，对于第二种情况可以枚举第一天走的最后的点，就转化为了第一天和初始时间为 $0$ 的情况了。

同样是预处理。固定起点和终点，对于一组方案，设 $(u,v,l,c)$ 为方案中经过的边，$x$ 为到 $u$ 的时间，将初始时间往后移 $[0,c-l-x]$ 这条边仍然能走，所以每次找到 $c-l-x$ 最小的边删掉，在剩下的边继续跑即可预处理出所有初始时间区间的答案。时间复杂度：$O(n^5)$，过不了。

显然可以枚举瓶颈边 $(u,v,l,c)$，则到 $u$ 的时间小于等于 $c-l$，$v$ 当天到后面点的时间等于 $c$ 时刻从 $v$ 出发的时间。所以可以设 $dis1_x$ 表示当天从 $x$ 到 $u$ 的最小时间，通过这个东西可以求出 $(u,v,l,c)$ 为瓶颈边的最大初始时刻。$dis2_x$ 表示当天 $c$ 时刻从 $v$ 到 $x$ 的最小时间。于是 $x\to y$ 的路径中瓶颈边为 $(u,v,l,c)$ 最小时间为 $dis1_x+dis2_y+l$。

然后搞个 vector 维护每对起点和终点经过所有瓶颈边对应的最小时间，先按照初始时间的限制排序，查询时二分出可行的后缀即可。

如果至少走两天，可以设 $f_{x,y}$ 表示当天从 $y$ 到 $x$ 的最小时间，$g_{x,y}$ 表示 $0$ 时刻从 $x$ 到 $y$ 的最小时间，这两个数组的求法和上面瓶颈边的 $dis1,dis2$ 差不多，然后枚举中转点 $i$，贡献即为 $\min\limits_{s-f_{u,i}\geq t}{s+g_{v,i}-t}$。

时间复杂度：$O(n^4+qn+q\log n)$。

具体细节见代码。

Code

#include <bits/stdc++.h>

// #define int int64_t

namespace FASTIO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf;
char getc() {
  return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> bool read(T &x) {
  x = 0; int f = 0; char ch = getc();
  while (ch < '0' || ch > '9') f |= ch == '-', ch = getc();
  while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = getc();
  x = (f ? -x : x); return 1;
}
template<typename A, typename ...B> bool read(A &x, B &...y) { return read(x) && read(y...); }
 
char obuf[1 << 21], *o1 = obuf, *o2 = obuf + (1 << 21) - 1;
void flush() { fwrite(obuf, 1, o1 - obuf, stdout), o1 = obuf; }
void putc(char x) { *o1++ = x; if (o1 == o2) flush(); }
template<class T> void write(T x) {
  if (!x) putc('0');
  if (x < 0) x = -x, putc('-');
  char c[40]; int tot = 0;
  while (x) c[++tot] = x % 10, x /= 10;
  for (int i = tot; i; --i) putc(c[i] + '0');
}
void write(char x) { putc(x); }
void write(char *x) { while (*x) putc(*x++); }
void write(const char *x) { while (*x) putc(*x++); }
template<typename A, typename ...B> void write(A x, B ...y) { write(x), write(y...); }
struct Flusher {
  ~Flusher() { flush(); }
} flusher;
} // namespace FASTIO
using FASTIO::read; using FASTIO::putc; using FASTIO::write;

const int kMaxN = 95, kMaxM = kMaxN * kMaxN / 2;
const int64_t kInf = 1e18;

int n, m, q;
int u[kMaxM], v[kMaxM];
int64_t s, l[kMaxM], c[kMaxM], f[kMaxN][kMaxN], g[kMaxN][kMaxN], dis1[kMaxN], dis2[kMaxN];
std::vector<std::tuple<int, int64_t, int64_t>> G[kMaxN];
std::vector<std::pair<int64_t, int64_t>> vec[kMaxN][kMaxN];

void dijkstra1(int x, int64_t t) {
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) {
    dis1[i] = kInf, vis[i] = 0;
  }
  std::queue<int> q;
  q.emplace(x), dis1[x] = 0;
  for (int c = 1; c <= n; ++c) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && (!u || dis1[i] < dis1[u]))
        u = i;
    if (!u || dis1[u] >= 1e17) break;
    vis[u] = 1;
    for (auto [v, l, c] : G[u]) {
      if (t - dis1[u] - l < 0) continue;
      if (t - dis1[u] <= c) dis1[v] = std::min(dis1[v], dis1[u] + l);
    }
  }
}

void dijkstra2(int x, int64_t t) {
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) {
    dis2[i] = kInf, vis[i] = 0;
  }
  std::queue<int> q;
  q.emplace(x), dis2[x] = 0;
  for (int c = 1; c <= n; ++c) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && (!u || dis2[i] < dis2[u]))
        u = i;
    if (!u || dis2[u] >= 1e17) break;
    vis[u] = 1;
    for (auto [v, l, c] : G[u]) {
      int64_t val = dis2[u] + t;
      if (val % s <= c - l) dis2[v] = std::min(dis2[v], dis2[u] + l);
    }
  }
} 

void dijkstra3(int x, int64_t t) {
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) {
    dis1[i] = kInf, vis[i] = 0;
  }
  std::queue<int> q;
  q.emplace(x), dis1[x] = 0;
  for (int c = 1; c <= n; ++c) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && (!u || dis1[i] < dis1[u]))
        u = i;
    if (!u || dis1[u] >= 1e17) break;
    vis[u] = 1;
    for (auto [v, l, c] : G[u]) {
      if (t - dis1[u] - l < 0) continue;
      if (t - dis1[u] > c) dis1[v] = std::min(dis1[v], dis1[u] + t - dis1[u] - c + l);
      else dis1[v] = std::min(dis1[v], dis1[u] + l);
    }
  }
}

void dijkstra4(int x, int64_t t) {
  static bool vis[kMaxN];
  for (int i = 1; i <= n; ++i) {
    dis2[i] = kInf, vis[i] = 0;
  }
  std::queue<int> q;
  q.emplace(x), dis2[x] = 0;
  for (int c = 1; c <= n; ++c) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && (!u || dis2[i] < dis2[u]))
        u = i;
    if (!u || dis2[u] >= 1e17) break;
    vis[u] = 1;
    for (auto [v, l, c] : G[u]) {
      int64_t val = dis2[u] + t;
      if (val % s > c - l) val += s - val % s;
      dis2[v] = std::min(dis2[v], val - t + l);
    }
  }
}

int64_t solve(int u, int v, int64_t t) {
  int64_t res = kInf;
  auto it = std::lower_bound(vec[u][v].begin(), vec[u][v].end(), std::pair<int64_t, int64_t>{t, 0});
  if (it != vec[u][v].end()) res = std::min(res, it->second);
  for (int i = 1; i <= n; ++i) {
    if (s - f[i][u] >= t) res = std::min(res, s + g[i][v] - t);
  }
  return res;
}

void dickdreamer() {
  read(n, m, s, q);
  for (int i = 1; i <= m; ++i) {
    read(u[i], v[i], l[i], c[i]);
    ++u[i], ++v[i];
    G[u[i]].emplace_back(v[i], l[i], c[i]), G[v[i]].emplace_back(u[i], l[i], c[i]);
  }
  for (int i = 1; i <= m; ++i) {
    dijkstra1(u[i], c[i] - l[i]), dijkstra2(v[i], c[i]);
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k <= n; ++k) {
        vec[j][k].emplace_back(c[i] - l[i] - dis1[j], dis1[j] + dis2[k] + l[i]);
      }
    }

    dijkstra1(v[i], c[i] - l[i]), dijkstra2(u[i], c[i]);
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k <= n; ++k) {
        vec[j][k].emplace_back(c[i] - l[i] - dis1[j], dis1[j] + dis2[k] + l[i]);
      }
    }
  }
  
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      std::sort(vec[i][j].begin(), vec[i][j].end());
      for (int k = (int)vec[i][j].size() - 2; k >= 0; --k) {
        vec[i][j][k].second = std::min(vec[i][j][k].second, vec[i][j][k + 1].second);
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    dijkstra3(i, s), dijkstra4(i, 0);
    for (int j = 1; j <= n; ++j) {
      f[i][j] = dis1[j], g[i][j] = dis2[j];
    }
  }
  for (int c = 1; c <= q; ++c) {
    int u, v; int64_t t;
    read(u, v, t);
    ++u, ++v;
    write(solve(u, v, t), '\n');
  }
}

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