P16068 [CSPro 32] 彩色路径

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。

西西艾弗岛的路线图可以看作是一个具有 $N$ 个节点和 $M$ 条有向边的图。第 $i$ 个节点（$0 \le i < N$）有一个颜色标签 $C[i] \in \{0, 1, \cdots, K - 1\}$，第 $j$ 条边（$0 \le j < M$）从节点 $U[j]$ 指向节点 $V[j]$，长度为 $D[j]$。 对于游客顿顿来说，理想的观光路线应满足以下条件： - 是一条从节点 $0$ 到节点 $N - 1$ 的简单路径； - 是一条彩色路径，即路径上每个节点的颜色标签均不相同； - 并且包含的节点数小于或等于 $L$。 具体而言，理想的观光路线是一个节点序列，例如 $(t_0, t_1, \cdots, t_{q-1})$，满足以下所有要求： - 对于每个 $i$（$0 \le i < q - 1$），存在一条从节点 $t_i$ 到节点 $t_{i+1}$ 的有向边。 - $t_0 = 0$ 且 $t_{q-1} = N - 1$ - 对于每对 $i, j$ （$0 \le i < j < q$），都有 $C[t_i] \ne C[t_j]$。 - $q \le L$ 一条路径的长度定义为边的总长度。你的任务是找到满足游客顿顿所有要求的**最长**观光路线。

从标准输入读入数据。 输入共五行。 输入的第一行包含四个正整数 $N、M、L$ 和 $K$，分别表示图的节点数、边数、理想观光路线的节点数上限和颜色标签范围。 输入的第二行包含 $N$ 个整数 $C[0], C[1], \cdots, C[N - 1]$，表示图中每个节点的颜色标签。 接下来输入边的信息。 输入的第三行包含 $M$ 个整数 $U[0], U[1], \cdots, U[M - 1]$，表示每条有向边的起点； 输入的第四行包含 $M$ 个整数 $V[0], V[1], \cdots, V[M - 1]$，表示每条有向边的终点； 输入的第五行包含 $M$ 个整数 $D[0], D[1], \cdots, D[M - 1]$，表示每条有向边的长度。 输入数据保证不存在起点终点相同的边，如 $(u, u)$；每条有向边 $(u, v)$ 仅会出现一次，但不排除 $(u, v)$ 和 $(v, u)$ 可能同时存在。

输出到标准输出。 输出一个数，表示理想观光路线的最大长度。

### 样例解释 以下是示例图，其中黑色和红色数字分别表示节点编号和边的长度。 :::align{center}  ::: 如下表所示，在不超过四个节点的限制下，共有五条从节点 $0$ 到节点 $5$ 的**彩色路径**。其中最长的一条是 $(0, 1, 5)$，长度为 $9$。 | 彩色路径 | 节点数 | 长度 | |:------------:|:------:|:----:| | $(0, 1, 3, 5)$ | $4$ | $7$ | | $(0, 1, 4, 5)$ | ^ | $4$ | | $(0, 2, 4, 5)$ | ^ | $8$ | | $(0, 1, 5)$ | $3$ | $9$ | | $(0, 4, 5)$ | ^ | $5$ | ### 子任务 $20\%$ 的测试数据满足：对于每个 $i$（$0 \le i < N - 1$），有 $C[i] \le C[i + 1]$，以及对于每个 $j$（$0 \le j < M$），有 $U[j] < V[j]$。 另有 $30\%$ 测试数据满足：$K \le 15$。 全部的测试数据满足： - $2 \le N \le 100$ - $1 \le M \le 5000$ - $2 \le L \le 9 \le K \le 30$ - $C[0] = 0$ 且 $C[N - 1] = K - 1$ - 对于每个 $i$（$1 \le i \le N - 2$）： $$ \begin{aligned} &1 \le C[i] \le K - 2 \end{aligned} $$ - 对于每个 $j$（$0 \le j < M$）： $$ \begin{aligned} &0 \le U[j], V[j] < N \\ &C[U[j]] \ne C[V[j]] \\ &1 \le D[j] \le 10^6 \end{aligned} $$ - 至少存在一条从节点 $0$ 到节点 $N - 1$ 的彩色路径，节点数不超过 $L$。