首页 > 试题广场 >

小红的旅游攻略

[编程题]小红的旅游攻略
  • 热度指数：43 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红是小红书的一个博主，她有很多的粉丝，有一些粉丝想让小红出一篇上尾市的旅游攻略。

上尾市有 n 个景点，有 m 条旅游路线，每个景点的攻略价值是 a ，要花费 h 时间浏览，不同景点之间的交通时间为 w 。

小红最多会选择3个相邻的景点，然后按顺序将景点写进攻略，她需要保证每个景点的浏览时间加上景点之间的交通时间总和不超过 k ，并且使得攻略的价值尽可能大，即景点的总价值尽可能大。

求小红的攻略的最大价值。

输入描述:
第一行输入三个整数 n,m(1 \leq n,m \leq 10^5),k(1 \leq k \leq 10^9) ，含义如题目描述所示。

第二行输入 n 个整数表示数组 a(1 \leq a_i \leq 10^9) 。

第三行输入 n 个整数表示数组 h(1 \leq h_i \leq 10^9) 。

接下来 m 行，每行输入三个整数 u,v(1 \leq u,v \leq n),w(1 \leq w \leq 10^9) 表示景点 u,v 之间的交通时间为 w 。


输出描述:
输出一个整数表示答案。
示例1

输入

4 4 8
4 3 2 1
1 2 3 4
1 2 1
2 3 1
2 4 1
3 4 1

输出

9

说明

路线3-2-1的价值为：4+3+2=9，耗费的时间为1+1+2+1+3=8
路线1-2-3也是一样的，都是最优方案。
可以证明，答案最大不超过9。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

图 小红书 排序
难度：
0条回答 46浏览

热门推荐

相关试题

小红的旅游攻略

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号