340. 【22CSPS提高组】假期计划(holiday) 中等

小熊的地图上有 $n$ 个点，其中编号为 $1$ 的是它的家、编号为 $2, 3, . . . , n$ 的都是景点。部分点对之间有双向直达的公交线路。如果点 $x$ 与 $z_1$、$z_1$ 与 $z_2$、……、$z_{k−1}$ 与 $z_k$、$z_k$ 与 $y$ 之间均有直达的线路，那么我们称 $x$ 与 $y$ 之间的行程可转车 $k$ 次通达；特别地，如果点 $x$ 与 $y$ 之间有直达的线路，则称可转车 $0$ 次通达。 很快就要放假了，小熊计划从家出发去 $4$ 个不同的景点游玩，完成 $5$ 段行程后回家：家 → 景点 A → 景点 B → 景点 C → 景点 D → 家且每段行程最多转车 $k$ 次。转车时经过的点没有任何限制，既可以是家、也可以是景点，还可以重复经过相同的点。例如，在景点 A → 景点 B 的这段行程中，转车时经过的点可以是家、也可以是景点 C，还可以是景点 D → 家这段行程转车时经过的点。 假设每个景点都有一个分数，请帮小熊规划一个行程，使得小熊访问的四个不同景点的分数之和最大。