← 返回比赛
已结束 GESP巅峰赛#26
← 上一题 下一题 →

A5305 | 奇怪的集市

时间限制2s
内存限制1024MB
通过 / 提交0/0

题目描述

$Alice$ 准备加入一个奇怪的集市，在这个集市中有一些奇怪的规则。

在集市中，有一些摊主，摊主们有一些关系，比如如果你给摊主 $u$ 元 ， 他可以把你推荐给他的一个朋友 $v_i$，需要支付费用 $k_i$;

同时集市中的人也是及其护短的，如果集市中的一些人，可以通过一些中介关系，任意两个人可以相互介绍到，我们把这些人当作一个小团体，在小团体中相互介绍，可以免除介绍费。

同时，如果说你拜访了集市中的某个人，如果是第一次拜访，可以获得 $w_i$ 元的礼物，

问 $Alice$ 现在带了 $W$ 元钱， 和 $P$ 件礼物，在一次操作中， $Alice$ 可以使用一个礼物免除介绍费， $Alice$ 选择在明天拜访这个集市，他可以从任意一个摊主开始，第一次拜访不需要介绍费。问经过一天的拜访，Alice 最多可以剩的多少钱？

输入格式

* 第 1 行：四个整数，分别为摊主数量 $N$、推荐关系数量 $M$、初始预算 $W$、礼物券数量 $P$。
* 第 2 行：$N$ 个整数，第 $i$ 个为摊主 $i$ 的礼物价值 $w_i$。
* 接下来 $M$ 行：每行三个整数 $u,v,k$，表示一条从 $u$ 指向 $v$ 的推荐边，费用为 $k$。

输出格式

输出一个整数，表示阿丽丝最多可以剩下多少钱。

输入输出样例

输入 #1
3 2 10 0
5 6 7
1 2 3
2 3 4
输出 #1
21
输入 #2
4 5 50 1
10 20 30 40
1 2 10
2 1 10
2 3 25
3 4 30
4 3 30
输出 #2
150
输入 #3
5 2 100 2
5 5 5 50 50
1 2 10
4 5 20
输出 #3
200
C++ 编辑器
输入
输出