P10122: 宝藏(treasure)

---

【题目描述】

【题目描述】
壮壮是一个爱探险的孩子。一天，他爬上了一座山，然后利用先进的遥感技术了解到了整座山的地形和内部构造。
他发现这座山一共有N个山洞和M个暗道。每一个山洞里都有宝藏，第i个山洞里有无限份价值为Ai的宝藏，壮壮经过山洞i，就会领取山洞i中的一份宝藏(每次经过都能领取一份)。
每一个暗道都连通两个山洞，第i个暗道连通了山洞Xi和Yi，壮壮可以穿过暗道i从山洞xi到达Yi，但是不可以穿过暗道i从山洞Yi到达xi，但无论怎么穿过暗道i，都要耗费一定的体力值Zi。
得知这些探洞信息后，壮壮马上开始准备去寻宝藏。已知壮壮的体力值上限为T，他最多只能耗费T的体力值。壮壮可以从任意一个山洞开始他的探索，但是只能穿过暗道去到别的山洞。
他每到达一个山洞，就会领取山洞中的一份宝藏。他想知道，他最多可以获得的宝藏价值之和为多少?
【输入格式】
第一行三个整数N,M和T，分别对应山洞的数量，暗道的数量，体力值上限。
第二行N个整数，第i个数是Ai，表示山洞i中的宝藏价值。
接下来M行，每行都有三个数xi，Yi和Zi，分别表示山洞i连接的两个山洞的编号和穿过这个暗道所要耗费的体力值。
【输出格式】
输出一个整数，表示耗费的体力值不超过T时，壮壮最多能获得的宝藏价值之和。
【输入样例1】
5 6 10
5 5 6 3 2
2 5 1
1 3 6
3 4 2
4 5 3
4 5 10
3 5 10
【输出样例1】
14
【样例解释】

样例中每一个点、边的情况如图所示，最优的走法是1->3->4。
【数据规模】
10%的数据是题目的馈赠。
对于30%的数据，1≤N≤10,1≤M≤20
对于50%的数据，1≤N≤20，1≤M≤50
对于70%的数据，1≤N≤150，1≤M≤500
对于100%的数据，1≤Zi,T≤500，1≤N,Xi,Yi≤1000,1≤M≤10000，0≤Ai≤10000
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

题目类型~

2023广西进阶组第三题 

咻咻~

提交答案 状态 返回