[NOI2020] 美食家

GitHub跳转原题关系图返回列表

通过将边权不超过 5 的有向图拆点为 5n 个状态，把按天动态规划转化为 (max, +) 矩阵乘法，并利用二进制预处理矩阵幂与向量乘法在 O((5n)^3 log T + k(5n)^2 log T) 内解决。

OJ: luogu

题目 ID: P6772

难度:提高+/省选-

标签:动态规划矩阵快速幂拆点倍增

创建: 2026-10-23 23:04

更新: 2026-10-26 14:16

形式化题目

给定一张包含 $n$ 个点、 $m$ 条有向边的图（无自环，允许重边），每条边 $(u, v, w)$ 具有通行耗时 $w \in [1, 5]$ 。每个点 $i$ 具有常态权值 $c_i$ 。每次到达点 $i$ （包括第 $0$ 天起点以及后续到达），都会获得愉悦值 $c_i$ 并必须立即沿某条出边离开，不能在途中停留。给定 $k$ 次临时增益活动 $(t_i, x_i, y_i)$ ，表示如果在第 $t_i$ 天恰好到达点 $x_i$ ，可以额外获得愉悦值 $y_i$ 。求从点 $1$ 出发（第 $0$ 天），恰好在第 $T$ 天回到点 $1$ 的最大愉悦值之和。若无法在第 $T$ 天回到点 $1$ ，输出 $-1$ 。

暴力解法

思路

不考虑 $T \le 10^9$ 的巨大天数，先建立最直接的状态转移方程。

定义 $dp(t, u)$ 表示在第 $t$ 天恰好到达城市 $u$ 所能获得的最大愉悦值之和。因为通行每条边需要花费 $w$ 天，所以第 $t$ 天到达城市 $v$ 必然是在第 $t-w$ 天从某个城市 $u$ 沿边 $(u, v, w)$ 出发。因此状态转移方程为：

dp(t, v) = \max_{(u, v, w) \in E, t \ge w} \{ dp(t-w, u) \} + c_v + (\text{若第 } t \text{ 天在 } v \text{ 存在美食节，加上 } y)

初始状态： $dp(0, 1) = c_1$ ，其余均为 $-\infty$ 。
空间优化：因为 $w \le 5$ ，第 $t$ 天的状态仅依赖于 $t-5 \sim t-1$ 天的状态，可以通过对天数模 $6$ 进行滚动数组压缩，空间复杂度仅为 $O(n)$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102/**
 * brute.cpp：小数据/低天数暴力解（按天数动态规划），用于帮助理解题意与对拍。
 * 为什么只适合小数据：
 * 朴素 DP 外层需要枚举每一天 t 从 1 到 T，内层枚举所有有向边，
 * 时间复杂度为 O(T * m)。
 * 当 T <= 50000 时能在 1 秒内运行完毕（覆盖前 40% 数据），
 * 但当 T 达到 10^9 时，循环次数高达 10^9 * 500 = 5 * 10^11，会严重超时（TLE）。
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 55;
const int MAXM = 505;
const int MAXK = 205;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;

int n, m, k;
ll T;
ll c[MAXN];

struct Edge {
    int u, v;
    int w;
} edges[MAXM];

struct Festival {
    ll t;
    int x;
    ll y;
} fest[MAXK];

// dp[t % 6][u]：到达城市 u，距离恰好还剩多久到达的记录；
// 这里直接用二维 vector dp[t][u] 支持 T <= 100000 的情况
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m >> T >> k)) return 0;
    for (int i = 1; i <= n; ++i) {
        cin >> c[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    for (int i = 1; i <= k; ++i) {
        cin >> fest[i].t >> fest[i].x >> fest[i].y;
    }

    // 预处理美食节哈希或查找表：小数据下可以用 map<(t, x), y>
    map<pair<ll, int>, ll> fest_map;
    for (int i = 1; i <= k; ++i) {
        fest_map[{fest[i].t, fest[i].x}] += fest[i].y;
    }

    // dp[t][u]：第 t 天恰好到达城市 u 的最大愉悦值
    // 为节省空间，只记录最近 6 天的状态 dp[0..5][u]
    vector<vector<ll>> dp(6, vector<ll>(n + 1, -INF));
    dp[0][1] = c[1];

    for (ll t = 1; t <= T; ++t) {
        int cur = t % 6;
        for (int i = 1; i <= n; ++i) {
            dp[cur][i] = -INF;
        }

        for (int i = 1; i <= m; ++i) {
            int u = edges[i].u;
            int v = edges[i].v;
            int w = edges[i].w;
            if (t >= w) {
                int prev = (t - w) % 6;
                if (dp[prev][u] >= 0) {
                    ll val = dp[prev][u] + c[v];
                    if (val > dp[cur][v]) {
                        dp[cur][v] = val;
                    }
                }
            }
        }

        // 检查第 t 天是否有美食节
        for (int i = 1; i <= n; ++i) {
            if (dp[cur][i] >= 0) {
                auto it = fest_map.find({t, i});
                if (it != fest_map.end()) {
                    dp[cur][i] += it->second;
                }
            }
        }
    }

    ll ans = dp[T % 6][1];
    if (ans < 0) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

复杂度

时间复杂度：每一天需要遍历所有 $m$ 条边，共转移 $T$ 天，时间复杂度为 $O(T \cdot m)$ 。
空间复杂度：由于采用模 $6$ 的滚动数组保存最近 $6$ 天的状态，空间复杂度为 $O(n)$ 。

瓶颈

在题目中 $T \le 52501$ 的测试点中，该暴力动态规划可以在时限内通过。但题目满分数据中 $T \le 10^9$ 。此时外层天数循环次数达到 $10^9 \times 500 = 5 \times 10^{11}$ 次计算，无法在时限内跑完。

瓶颈在于：虽然总天数 $T$ 极大，但图的结构和绝大部分时间内的转移规则是恒定不变的（美食节只有 $k \le 200$ 次）。我们需要将线性按天递推加速为对数级转移。

正解

思路

1. 广义矩阵乘法与 $(\max, +)$ 半环

在没有美食节时，考虑转移方程的形式：

dp(t, v) = \max_{u} \{ dp(t-1, u) + \text{边权} \}

这与经典矩阵乘法

C_{i, j} = \sum_{k} (A_{i, k} \times B_{k, j})

的结构完全同构，只需将标量加法替换为取最大值

\max

，标量乘法替换为普通加法

+

。在该代数系统（称为

(\max, +)

半环）中：

矩阵乘法定义为： $(A \times B)_{i, j} = \max_{k} \{ A_{i, k} + B_{k, j} \}$ ；
该矩阵乘法同样满足结合律 $(A \times B) \times C = A \times (B \times C)$ ；
零元为 $-\infty$ ，乘法单位元 $I$ 为对角线上全为 $0$ 、非对角线全为 $-\infty$ 的对角矩阵。

下表逐项对照 $(\max, +)$ 矩阵乘法与经典矩阵乘法的符号角色, 从上往下每一行都是一次符号替换, 对照着看就能把上面的转移式直接写成矩阵乘法:

符号角色	经典矩阵乘法	$(\max, +)$ 矩阵乘法
求和号 $\sum$ 处的合并运算	加法 $+$	取最大值 $\max$
相乘处的标量运算	标量乘法 $\times$	标量加法 $+$
零元	$0$	$-\infty$
乘法单位元 $I$	对角线全 $1$ 、其余全 $0$	对角线全 $0$ 、其余全 $-\infty$

整张表其实只有两个替换: 求和号处的 $+$ 换成 $\max$ , 相乘处的 $\times$ 换成 $+$ , 其余结构原样照搬. 于是经典矩阵乘法的结合律在新系统中原样成立, 矩阵快速幂的正确性不需要重新证明. 零元 $-\infty$ 表示不可达: 任何值与 $-\infty$ 相加仍是 $-\infty$ , 无效路径永远不会混进 $\max$ . 乘法单位元对角线取 $0$ 而不是 $1$ , 是因为「什么都不走」贡献的愉悦值恰好是 $0$ .

2. 边权 $1 \le w \le 5$ 的拆点技巧

由于有向边的通行时间 $w \in [1, 5]$ 不全为 $1$ ，不能直接在原图的邻接矩阵上做转移。注意到 $w$ 极小（最大仅为 $5$ ），我们可以使用经典的拆点法将非单位权有向图转化为等价的单位权图：将原图中的每个城市 $u$ 拆为 $5$ 个虚点 $(u, 0), (u, 1), (u, 2), (u, 3), (u, 4)$ ，其中状态 $(u, j)$ 表示“当前位于正在前往城市 $u$ 的途中，距离真正到达还剩 $j$ 天”：

内部连边：对 $j \in [1, 4]$ ，建立转移 $(u, j) \to (u, j-1)$ ，转移增益为 $0$ 。这表示每过一天，距离到达城市 $u$ 就少一天；
原图有向边：对于原图中的有向边 $(u, v, w)$ ，小 W 在到达城市 $u$ （即状态 $(u, 0)$ ）时决定沿该边出发，耗时 $w$ 天到达 $v$ 。这相当于经过 $1$ 天后，状态进入 $(v, w-1)$ ，并在最终到达时收获 $c_v$ 愉悦值。因此建立转移 $(u, 0) \to (v, w-1)$ ，转移增益为 $c_v$ （若存在重边，取最大的 $c_v$ 即可）。

下图把城市 $u$ 的 5 个虚点画成一组, 展示拆点产生的两类转移边(以一条原图边 $(u, v, w = 3)$ 为例), 重点看每条边旁标注的增益:

flowchart LR
  subgraph GU["城市 u 的 5 个虚点"]
    direction TB
    U4["(u, 4) 距到达 u 还剩 4 天"] -->|"增益 0"| U3["(u, 3) 还剩 3 天"]
    U3 -->|"增益 0"| U2["(u, 2) 还剩 2 天"]
    U2 -->|"增益 0"| U1["(u, 1) 还剩 1 天"]
    U1 -->|"增益 0"| U0["(u, 0) 已到达 u"]
  end
  subgraph GV["城市 v 的 5 个虚点 (以 w = 3 为例)"]
    direction TB
    V4["(v, 4) 距到达 v 还剩 4 天"] -->|"增益 0"| V3["(v, 3) 还剩 3 天"]
    V3 -->|"增益 0"| V2["(v, 2) 还剩 2 天"]
    V2 -->|"增益 0"| V1["(v, 1) 还剩 1 天"]
    V1 -->|"增益 0"| V0["(v, 0) 已到达 v"]
  end
  U0 -->|"原图边 (u, v, w = 3), 增益 c_v"| V2

每组内的链是内部边 $(u, j) \to (u, j-1)$ , 每走一步恰好过 1 天且增益为 $0$ , 所以 $(u, 0)$ 就表示真的到达了 $u$ . 跨组边从 $(u, 0)$ 出发, 却落在 $(v, w-1)$ 而不是 $(v, 0)$ : 出发后还要沿 $v$ 的内部链再走 $w-1$ 天才真正到达 $v$ . 增益 $c_v$ 挂在跨组边上, 内部链增益恒为 $0$ , 这样每到达一座城市就恰好计入一次 $c_v$ , 不会因等待天数被重复计算.

拆点后，新图的点数变为 $N = 5n \le 250$ 。此时所有的转移都是跨越恰好 $1$ 天的单位转移，可以完整写成一个 $N \times N$ 的一步转移矩阵 $M$ 。

3. 美食节划分与向量乘矩阵优化

图中有 $k \le 200$ 次美食节。我们将所有美食节按时间升序排序为 $t_1 \le t_2 \le \dots \le t_k$ ，并令 $t_0 = 0$ 。整个时间轴被切分为最多 $k+1$ 个连续的无美食节区间 $[t_{i-1}, t_i]$ ：

在区间 $(t_{i-1}, t_i)$ 内，转移完全等价于乘以 $M^{\Delta t}$ （其中 $\Delta t = t_i - t_{i-1}$ ）；
到达第 $t_i$ 天后，将对应美食节城市 $x_i$ 的状态加上额外愉悦值 $y_i$ （若该状态当前可达）。

如果对每个区间都重新计算矩阵幂 $M^{\Delta t}$ ，每次计算需要 $O(N^3 \log \Delta t)$ ，总复杂度为 $O(k N^3 \log T)$ ，计算量接近 $200 \times 30 \times 250^3 \approx 9.3 \times 10^{10}$ ，依然无法通过。

关键优化：我们并不需要维护完整的 $N \times N$ 状态矩阵，而只需要维护一个 $1 \times N$ 的行向量 $F$ （其中 $F_j$ 表示当前天到达状态 $j$ 的最大愉悦值）。行向量乘以矩阵的复杂度仅为 $O(N^2)$ 。因此：

在开头预处理出矩阵的倍增幂 $M^{2^0}, M^{2^1}, \dots, M^{2^{29}}$ ，共需 $30$ 次矩阵相乘，耗时 $O(N^3 \log T)$ ；
转移每一段 $\Delta t$ 时，将 $\Delta t$ 拆为二进制位，每一位对应一次行向量乘以预处理好的矩阵，耗时仅 $O(N^2)$ ；
总共只需要进行 $(k+1) \log T$ 次向量乘矩阵，计算量降至 $200 \times 30 \times 250^2 \approx 3.75 \times 10^8$ 次运算，配合非负剪枝后可以在时限内轻松通过。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 23:04
 * update_at: 2026-10-23 23:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 55;
const int MAX_STATES = 255;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;

int n, m, k;
ll T;
ll c[MAXN];
int tot_states; // N = 5 * n

// 拆点编号映射：u in [1, n], j in [0, 4]
// j 表示距离到达城市 u 还要经过 j 天
inline int get_id(int u, int j) {
    return j * n + u;
}

// (max, +) 矩阵
struct Matrix {
    ll mat[MAX_STATES][MAX_STATES];

    Matrix() {
        for (int i = 1; i <= tot_states; ++i) {
            for (int j = 1; j <= tot_states; ++j) {
                mat[i][j] = -INF;
            }
        }
    }
};

// 矩阵乘法 C = A * B 在 (max, +) 半环下
Matrix multiply(const Matrix &A, const Matrix &B) {
    Matrix C;
    for (int i = 1; i <= tot_states; ++i) {
        for (int mid = 1; mid <= tot_states; ++mid) {
            if (A.mat[i][mid] < 0) continue;
            for (int j = 1; j <= tot_states; ++j) {
                if (B.mat[mid][j] < 0) continue;
                ll val = A.mat[i][mid] + B.mat[mid][j];
                if (val > C.mat[i][j]) {
                    C.mat[i][j] = val;
                }
            }
        }
    }
    return C;
}

// 行向量乘矩阵：vec = vec * A 在 (max, +) 半环下
void vec_multiply(vector<ll> &vec, const Matrix &A) {
    vector<ll> res(tot_states + 1, -INF);
    for (int mid = 1; mid <= tot_states; ++mid) {
        if (vec[mid] < 0) continue;
        for (int j = 1; j <= tot_states; ++j) {
            if (A.mat[mid][j] < 0) continue;
            ll val = vec[mid] + A.mat[mid][j];
            if (val > res[j]) {
                res[j] = val;
            }
        }
    }
    vec = std::move(res);
}

// 预处理矩阵倍增幂：pow_mat[p] = M^(2^p)
Matrix pow_mat[32];

struct Festival {
    ll t;
    int x;
    ll y;
} fest[205];

bool cmp_fest(const Festival &a, const Festival &b) {
    return a.t < b.t;
}

void solve() {
    tot_states = 5 * n;

    // 构建基础一步转移矩阵 M
    Matrix M;
    // 1. 虚点内部连边：距离到达 u 还剩 j 天，走 1 天变为还剩 j-1 天
    for (int u = 1; u <= n; ++u) {
        for (int j = 1; j <= 4; ++j) {
            M.mat[get_id(u, j)][get_id(u, j - 1)] = 0;
        }
    }
    // 2. 原图中的有向边 (u, v, w)：从到达 u 的瞬间出发，耗时 w 天到达 v
    // 相当于下一步处于状态 (v, w - 1)，到达 v 时可获得 c[v] 愉悦值
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        int from_id = get_id(u, 0);
        int to_id = get_id(v, w - 1);
        if (c[v] > M.mat[from_id][to_id]) {
            M.mat[from_id][to_id] = c[v];
        }
    }

    for (int i = 1; i <= k; ++i) {
        cin >> fest[i].t >> fest[i].x >> fest[i].y;
    }
    sort(fest + 1, fest + k + 1, cmp_fest);

    // 预处理倍增矩阵幂
    pow_mat[0] = M;
    for (int p = 1; p <= 30; ++p) {
        pow_mat[p] = multiply(pow_mat[p - 1], pow_mat[p - 1]);
    }

    // 初始状态向量：第 0 天位于城市 1（get_id(1, 0)），获得愉悦值 c[1]
    vector<ll> F(tot_states + 1, -INF);
    F[get_id(1, 0)] = c[1];

    ll cur_t = 0;
    for (int i = 1; i <= k; ++i) {
        ll dt = fest[i].t - cur_t;
        if (dt > 0) {
            for (int p = 0; p <= 30; ++p) {
                if ((dt >> p) & 1) {
                    vec_multiply(F, pow_mat[p]);
                }
            }
            cur_t = fest[i].t;
        }
        int target_id = get_id(fest[i].x, 0);
        if (F[target_id] >= 0) {
            F[target_id] += fest[i].y;
        }
    }

    // 跨越最后一段无美食节的时间直到 T
    if (T > cur_t) {
        ll dt = T - cur_t;
        for (int p = 0; p <= 30; ++p) {
            if ((dt >> p) & 1) {
                vec_multiply(F, pow_mat[p]);
            }
        }
    }

    ll ans = F[get_id(1, 0)];
    if (ans < 0) {
        cout << -1 << "\n";
    } else {
        cout << ans << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    while (cin >> n >> m >> T >> k) {
        for (int i = 1; i <= n; ++i) {
            cin >> c[i];
        }
        solve();
    }

    return 0;
}

复杂度

时间复杂度：
- 预处理矩阵倍增幂：计算 $\log T \approx 30$ 次 $N \times N$ 矩阵相乘，耗时 $O(N^3 \log T) = O((5n)^3 \log T)$ ；
- 美食节按时间排序： $O(k \log k)$ ；
- 跨越 $k+1$ 段区间的向量转移：共进行最多 $(k+1) \log T$ 次向量乘矩阵，每次耗时 $O(N^2)$ ，总耗时 $O(k N^2 \log T) = O(k (5n)^2 \log T)$ ；
- 总时间复杂度为 $O((5n)^3 \log T + k (5n)^2 \log T)$ 。当 $n = 50, k = 200, T = 10^9$ 时， $N = 250$ ，常数较小且稀疏剪枝，运行时间在 0.5 秒左右，完全满足时限要求。
空间复杂度：
- 存储 $30$ 个 $250 \times 250$ 的 long long 转移矩阵，空间占用约为 $30 \times 250 \times 250 \times 8 \text{ Bytes} \approx 15 \text{ MB}$ ；
- 辅助向量和美食节数组空间为 $O(5n + k)$ ；
- 总空间复杂度为 $O(N^2 \log T) = O((5n)^2 \log T)$ ，远小于题目限制的 512 MB。

总结

本题的关键在于两个核心转化的有机结合：

拆点降维：利用边权 $w \le 5$ 的限制，将每座城市拆成 5 个等待状态，将带权边转化为单位步长的状态机转移，从而使问题能够套用矩阵快速幂；
向量乘法降阶：利用状态只需要从起点单向推进的特点，将 $k$ 段区间的全矩阵快速幂优化为“预处理矩阵倍增幂 + 向量右乘”，把瓶颈项的复杂度从 $O(k N^3 \log T)$ 降为 $O(k N^2 \log T)$ 。

P6772 [NOI2020] 美食家

题目描述

坐落在 Bzeroth 大陆上的精灵王国击退地灾军团的入侵后，经过十余年的休养生息，重新成为了一片欣欣向荣的乐土，吸引着八方游客。小 W 是一位游历过世界各地的著名美食家，现在也慕名来到了精灵王国。

精灵王国共有 $n$ 座城市，城市从 $1$ 到 $n$ 编号，其中城市 $i$ 的美食能为小 W 提供 $c_i$ 的愉悦值。精灵王国的城市通过 $m$ 条单向道路连接，道路从 $1$ 到 $m$ 编号，其中道路 $i$ 的起点为城市 $u_i$ ，终点为城市 $v_i$ ，沿它通行需要花费 $w_i$ 天。也就是说，若小 W 在第 $d$ 天从城市 $u_i$ 沿道路 $i$ 通行，那么他会在第 $d + w_i$ 天到达城市 $v_i$ 。

小 W 计划在精灵王国进行一场为期 $T$ 天的旅行，更具体地：他会在第 $0$ 天从城市 $1$ 出发，经过 $T$ 天的旅行，最终在恰好第 $T$ 天回到城市 $1$ 结束旅行。由于小 W 是一位美食家，每当他到达一座城市时（包括第 $0$ 天和第 $T$ 天的城市 $1$ ），他都会品尝该城市的美食并获得其所提供的愉悦值，若小 W 多次到达同一座城市，他将获得多次愉悦值。注意旅行途中小 W 不能在任何城市停留，即当他到达一座城市且还未结束旅行时，他当天必须立即从该城市出发前往其他城市。

对于上图，小 W 一种为期 $11$ 天的可行旅游方案为 $1 \to 2 \to 1 \to 2 \to 3 \to 1$ ：

第 $0$ 天，小 W 从城市 $1$ 开始旅行，获得愉悦值 $1$ 并向城市 $2$ 出发。
第 $1$ 天，小 W 到达城市 $2$ ，获得愉悦值 $3$ 并向城市 $1$ 出发。
第 $4$ 天，小 W 到达城市 $1$ ，获得愉悦值 $1$ 并向城市 $2$ 出发。
第 $5$ 天，小 W 到达城市 $2$ ，获得愉悦值 $3$ 并向城市 $3$ 出发。
第 $7$ 天，小 W 到达城市 $3$ ，获得愉悦值 $4$ 并向城市 $1$ 出发。
第 $11$ 天，小 W 到达城市 $1$ ，获得愉悦值 $1$ 并结束旅行。
小 W 在该旅行中获得的愉悦值之和为 $13$ 。

此外，精灵王国会在不同的时间举办 $k$ 次美食节。具体来说，第 $i$ 次美食节将于第 $t_i$ 天在城市 $x_i$ 举办，若小 W 第 $t_i$ 天时恰好在城市 $x_i$ ，那么他在品尝城市 $x_i$ 的美食时会额外得到 $y_i$ 的愉悦值。现在小 W 想请作为精灵王国接待使者的你帮他算出，他在旅行中能获得的愉悦值之和的最大值。

输入格式

从标准输入中读入数据。

第一行四个整数 $n, m, T, k$ ，依次表示城市数、道路条数、旅行天数与美食节次数。

第二行 $n$ 个整数 $c_i$ ，表示每座城市的美食所能提供的愉悦值。接下来 $m$ 行每行三个整数 $u_i, v_i, w_i$ ，依次表示每条道路的起点、终点与通行天数。

最后 $k$ 行每行三个整数 $t_i, x_i, y_i$ ，依次表示每次美食节的举办时间、举办城市与提供的额外愉悦值。

本题中数据保证：

对所有 $1 \leq i \leq m$ ，有 $u_i\neq v_i$ 。但数据中可能存在路线重复的单向道路，即可能存在 $1 \leq i < j \leq m$ ，使得 $u_i = u_j, v_i = v_j$ 。
对每座城市都满足：至少存在一条以该城市为起点的单向道路。
每次美食节的举办时间 $t_i$ 互不相同。

输出格式

输出到标准输出中。

仅一行一个整数，表示小 W 通过旅行能获得的愉悦值之和的最大值。

若小 W 无法在第 $T$ 天回到城市 $1$ ，则输出 $-1$ 。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

说明/提示

样例 1 解释

该样例为题目描述中的例子，最优旅行方案见题目描述。

样例 2 解释

最优方案为 $1 \to 3 \to 4 \to 2 \to 3 \to 4 \to 1$ 。

第 $0$ 天，小 W 从城市 $1$ 开始旅行，获得愉悦值 $3$ 并沿道路 $3$ 通行。
第 $2$ 天，小 W 到达城市 $3$ ，获得愉悦值 $2$ 并沿道路 $4$ 通行。
第 $5$ 天，小 W 到达城市 $4$ ，由于美食节获得愉悦值 $20 + 4$ 并沿道路 $7$ 通行。
第 $6$ 天，小 W 到达城市 $2$ ，获得愉悦值 $1$ 并沿道路 $5$ 通行。
第 $8$ 天，小 W 到达城市 $3$ ，获得愉悦值 $2$ 并沿道路 $4$ 通行。
第 $11$ 天，小 W 到达城市 $4$ ，获得愉悦值 $4$ 并沿道路 $8$ 通行。
第 $16$ 天，小 W 到达城市 $1$ ，获得愉悦值 $3$ 并结束旅行。
小 W 获得的愉悦值之和为 $39$ 。

样例 3

见选手目录下的 delicacy/delicacy3.in 与 delicacy/delicacy3.ans。

该样例满足 $k=0$

测试点约束

对于所有测试点：

$1 \leq n \leq 50$ ， $n \leq m \leq 501$ ， $0 \leq k \leq 200$ ， $1 \leq t_i \leq T \leq 10^9$ 。

$1 \leq w_i \leq 5$ ， $1 \leq c_i \leq 52501$ ， $1 \leq u_i, v_i, x_i \leq n$ ， $1 \leq y_i \leq 10^9$ 。

每个测试点的具体限制见下表：

测试点编号	$n$	$m$	$T$	特殊限制
$1\sim 4$	$\le 5$	$\le 50$	$\le 5$	无
$5\sim 8$	$\le 50$	$\le 50$	$\le 52501$	无
$9\sim 10$	$\le 50$	$\le 50$	$\le 10^9$	A
$11\sim 13$	$\le 50$	$\le 50$	$\le 10^9$	$k=0$
$14\sim 15$	$\le 50$	$\le 50$	$\le 10^9$	$k\le 10$
$16\sim 17$	$\le 50$	$\le 50$	$\le 10^9$	无
$18\sim 20$	$\le 50$	$\le 501$	$\le 10^9$	无

特殊限制 A： $n = m$ 且 $u_i = i,v_i = (i \bmod n) + 1$ 。

[NOI2020] 美食家

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

1. 广义矩阵乘法与 (max⁡,+)(\max, +)(max,+) 半环

2. 边权 1≤w≤51 \le w \le 51≤w≤5 的拆点技巧

3. 美食节划分与向量乘矩阵优化

代码

复杂度

总结

1. 广义矩阵乘法与 $(\max, +)$ 半环

2. 边权 $1 \le w \le 5$ 的拆点技巧