Problem Link: LOJ3339

Solution

Sort the events by time.

Note that $w \leq 5$ , which means that we can separate each edge into edges of weight $1$ . Specifically, we can replace each node $i$ ( $0$ -indexed) with nodes $5 i, 5 i + 1, \dots, 5 i + 4$ handling edges of weight $1 \dots 5$ . Nodes $5 i + j$ and $5 i + (j + 1)$ for $0 \leq j < 4$ have an edge of weight $1$ and edges $u, v, w$ ( $0$ -indexed) are transformed into an edge $5 u + (w - 1) \to 5 v$ with weight $1$ .

Now that all edge weights are $1$ , we can use binary lifting to compute the answer. Let $j m p [i] [u] [v]$ represent the maximum total joy value if Xiao W travels for $2^{i}$ days from node $u$ to node $v$ , besides the food festivals and initial node. We compute transitions as follows:

j m p [i] [u] [v] = max_{0 \leq m i d < 5 n} (j m p [i - 1] [u] [m i d] + j m p [i - 1] [m i d] [v]) .

Each transition takes $O (n^{3})$ time, so computing the binary jump takes $O (n^{3} \log T)$ time.

Now that we have the binary lift, we can compute $d p [t] [v]$ , which represents the maximum joy Xiao W can get by travelling for $t$ days and ending at node $v$ , taking food festivals into consideration. We compute $d p$ for each food festival, as well as $t = 0$ and $t = T$ . Let $j o y [u] [v]$ represent the maxiumum joy Xiao W gets when travelling from $u$ to $v$ in $t_{i} - t_{i - 1}$ days, computed using the same transitions above. Then, the transitions for $d p$ are

d p [t_{i}] [u] = max_{0 \leq v < 5 n} (d p [t_{i - 1}] [v] + j o y [v] [u]) .

However, this leads to a time complexity of $O (k n^{3} \log T)$ , because we have to compute $j o y$ , which takes $O (n^{3} \log T)$ .

To make this faster, we can add new food festivals such that the difference between consecutive food festivals is a power of two, allowing us to use the previously-computed $j m p$ values without more computation. Using the same $d p$ transitions above, which takes $O (n^{2})$ , we achieve a time complexity of $O ((n^{3} + k n^{2}) \log T)$ .

Implementation

/**
 * @author n685
 * @brief
 * @date 2024-07-31 11:59:57
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
void bar() {}
#endif

template <class T> constexpr T INF = T{};
template <std::floating_point T>
constexpr T INF<T> = std::numeric_limits<T>::infinity();
template <> constexpr int INF<int> = 0x3f3f3f3f; // 1061109567
template <>
constexpr int64_t INF<int64_t> = 0x3f3f3f3f3f3f3f3f; // 4557430888798830399

constexpr int LG = std::bit_width<uint32_t>(1'000'000'000); // 30
template <class T> T &chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
  }
  return a;
}

struct Event {
  int64_t t;
  int x;
  int64_t y;
};

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::freopen("delicacy.in", "r", stdin);
  std::freopen("delicacy.out", "w", stdout);
#endif

  int n, m;
  int64_t t;
  int k;
  std::cin >> n >> m >> t >> k;
  std::vector<int64_t> c(5 * n);
  for (int i = 0; i < n; ++i) {
    std::cin >> c[5 * i];
  }
  std::array<std::vector<std::vector<int64_t>>, LG> jmp;
  jmp.fill(std::vector(5 * n, std::vector(5 * n, -INF<int64_t>)));
  for (int i = 0; i < n; ++i) {
    for (int j = 1; j <= 4; ++j) {
      jmp[0][5 * i + (j - 1)][5 * i + j] = 0;
    }
  }
  n = 5 * n;
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    std::cin >> u >> v >> w;
    --u;
    --v;
    u = 5 * u;
    v = 5 * v;
    chmax(jmp[0][u + (w - 1)][v], c[v]);
  }
  std::vector<Event> pe;
  pe.emplace_back(0, -1, -1);
  int64_t evt = 0;
  for (int i = 0; i < k; ++i) {
    int64_t tt;
    int x;
    int64_t y;
    std::cin >> tt >> x >> y;
    x = 5 * (x - 1);
    if (tt != t) {
      pe.emplace_back(tt, x, y);
    } else {
      if (x == 0) {
        evt = y;
      }
    }
  }
  pe.emplace_back(t, 0, evt);
  std::ranges::sort(pe, {}, &Event::t);

  std::vector<Event> ev;
  ev.emplace_back(0, -1, -1);
  for (int i = 1; i < std::ssize(pe); ++i) {
    auto [tt, x, y] = pe[i];
    int64_t pt = ev.back().t;
    for (int j = LG - 1; j >= 0; --j) {
      if (tt - pt >= (int64_t{1} << j)) {
        ev.emplace_back(pt + (int64_t{1} << j), -1, -1);
        pt += int64_t{1} << j;
      }
    }
    ev.back().x = x;
    ev.back().y = y;
  }

  for (int l = 1; l < LG; ++l) {
    for (int mid = 0; mid < n; ++mid) {
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
          chmax(jmp[l][i][j], jmp[l - 1][i][mid] + jmp[l - 1][mid][j]);
        }
      }
    }
  }
  std::vector pre(n, -INF<int64_t>);
  pre[0] = c[0];
  for (int i = 1; i < std::ssize(ev); ++i) {
    auto [tt, x, y] = ev[i];
    int lg = std::bit_width<uint64_t>(tt - ev[i - 1].t) - 1;
    std::vector cur(n, -INF<int64_t>);
    for (int ini = 0; ini < n; ++ini) {
      for (int dest = 0; dest < n; ++dest) {
        chmax(cur[dest], pre[ini] + jmp[lg][ini][dest]);
      }
    }
    if (x != -1) {
      cur[x] += y;
    }
    pre.swap(cur);
  }
  if (pre[0] <= -INF<int64_t> / 2) {
    std::cout << "-1\n";
  } else {
    std::cout << pre[0] << '\n';
  }
}