题目内容

小红很喜欢旅游，目标是游遍全球。作为一个程序猿，小红想写个程序来规划自己的旅游路线。

现在小红来到了一个城市，这个城市有 $n$ 个景点，有 $m$ 条路连通这 $n$ 个景点。游览景点 $i$ 花费的时间为 $t_i$ ，获得的快乐值为 $h_i$ 。

思路：枚举 + 二分

这题至多游览三个景点，而且要求任意两个游览的景点，至多通过两条路径可以到达。

考虑游览的景点数：

• 一个，遍历所有景点即可
• 两个，枚举每条边即可
• 三个，枚举每个点 $x$ 的所有邻居，根据通过路径的时间和游览景点的时间从小到大排序。然后继续枚举点 $x$ 的邻居 $y$ ，再二分得到符合条件的邻居 $z$ 即可。

时间复杂度：$O(m\log m)$