2040：魔童闹海
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：5
解决：3
题目描述
背景：
我命由我不由天！
————《哪吒2：魔童闹海》
哪吒虽为魔丸转世，但心地善良，与灵珠敖丙结为好友，逆天改命。
一日，东海龙王敖广因触怒天庭，被无量仙翁囚禁于天元鼎中，龙宫和无数被敖广压的海底妖兽也一同被困。龙族危在旦夕，海底生灵面临浩劫。
哪吒不忍生灵涂炭，决定冒着风险，进入天元鼎，帮助龙族逃出生天。
问题：
天元鼎内部可以抽象成一个有 $N$ 个节点的有向图，节点间有 $M$ 条有向边相连。
其中：
1. 节点 $1$ 代表哪吒的起始位置。
2. 节点 $2$ 代表东海龙王敖广的位置。
3. 其余节点代表鼎内的通道或者关押海底妖兽的地点。
4. 每条边都有两个属性：权重（难度，消耗的法力值）和风险值。通过一条边会消耗相应的法力值，并增加相应的风险值。
哪吒需要到敖广处解救龙王。之后，他会联合一些妖兽和龙王的力量共同打开天元鼎的出口（节点 $N$）。
为了成功打开出口，需要满足以下条件：
1. 必须解救敖广：哪吒必须到达节点 $2$（敖广处），法力和风险也包含在内。
2. 妖兽助力：至少需要 $K$ 只妖兽参与才能打开出口。每个节点（哪吒的起始位置（节点 1）和龙王敖广的位置（节点 $2$）除外）都可能关押着妖兽，节点 $i$ 关押着 $\text{monster}_i$ 只妖兽。哪吒和敖广都可以沿途解救妖兽，使其加入队伍。
3. 法力限制： 哪吒的法力值有限，初始法力值为 $V$。每通过一条边，法力值会减少相应的权重。如果法力值降到 $0$ 或负数则无法继续前进。
4. 风险限制：天元鼎内危机重重，哪吒的总风险值不能超过 $R$。
5. 时间限制：由于天元鼎内的任何妖兽（包括哪吒和敖广）在 $T$ 时间后都会化为仙丹，所以哪吒必须在 $T$ 时间内到达出口。
请你计算哪吒成功解救龙王并带领至少 $K$ 只妖兽到达出口（节点 $N$）的最小法力消耗。
如果无法完成任务，输出 $-1。$
输入
第 $1$ 行：共 $6$ 个数，$N$（节点数量），$M$（边的数量），$K$（至少需要的妖兽数量），$V$（哪吒的初始法力值），$R$（最大风险值），$T$（最大时间）
第 $2$ 行：共 $n-2$ 个数，$\{monster_i\}_{i=3}^{n}$，表示每个节点关押的妖兽数量（节点 $1$ 和节点 $2$ 不关押妖兽，默认为 $0$）
第 $2$ 行：共 $n-2$ 个数，$\{monster_i\}_{i=3}^{n}$，表示每个节点关押的妖兽数量（节点 $1$ 和节点 $2$ 不关押妖兽，默认为 $0$）
第 $3$ 至 $m+2$ 行：每行包括 $4$ 个整数 $u$、$v$、$w$、$r$，表示从节点 $u$ 到节点 $v$ 有一条权重为 $w$，风险值为 $r$ 的有向边。
$
\begin{aligned}
1 &\leq N \leq 50, \quad 0 \leq M \leq \frac{N \times (N - 1)}{2}. \\
0 &\leq K \leq 100, \quad 1 \leq V \leq 100, \quad 0 \leq R \leq 100, \quad 0 \leq T \leq 20. \\
1 &\leq w, r \leq 10, \quad 0 \leq \{monster_i\}_{i=3}^{n} \leq 10
\end{aligned}
$
输出
一个整数：表示最小的法力消耗。如果无法完成任务，输出 $-1。$
样例输入-1 复制
5 6 2 100 50 10
1 1 1
1 2 10 5
1 3 5 2
2 4 15 8
3 4 8 3
4 5 20 10
3 5 12 4样例输出-1 复制
45样例输入-2 复制
5 7 5 80 95 40
4 10 5
4 2 6 6
1 2 1 2
1 3 6 9
3 4 5 3
2 5 4 6
5 2 6 1
3 5 2 9
样例输出-2 复制
5提示
样例解释：
路线：$1 \to 2 \to 4 \to 5$
妖兽：$1$(节点$4$)$ + 1$(节点$5$)$ = 2$
风险：$5 + 8 + 10 = 23$
法力：$10 + 15 + 20 = 45$
时间：$1 + 1 + 1 = 3$
