问题分析

这是一个在有向图上寻找最长路径的问题，需要处理：

• 极大时间范围 $T = 10^9$ 下的路径规划
• 边权较小（$1 \leq w_i \leq 5$）但路径长度极大
• 特定时间点的美食节额外收益
• 要求第 $T$ 天必须回到起点城市 $1$

核心思路

1. 状态扩展与周期处理

• 由于边权最大为 $5$，将每个城市扩展为 $5$ 个状态，表示"到达时间模 $5$ 的余数"
• 这样可以将时间维度从 $T$ 压缩到 $5n$ 个状态
• 通过状态扩展建立完整的转移关系

2. 矩阵快速幂优化

• 将状态转移关系表示为矩阵形式
• 利用矩阵快速幂在 $O(\log T)$ 时间内完成大规模状态转移
• 预处理 $2^k$ 次幂的转移矩阵，实现快速跳跃

3. 美食节分段处理

• 将时间轴按美食节发生时间分段
• 在每个时间段内使用矩阵快速幂进行批量转移
• 在美食节时间点进行特殊处理：为对应城市状态增加额外收益

4. 初始与终止条件

• 初始状态：第 $0$ 天在城市 $1$，获得基础愉悦值
• 终止条件：第 $T$ 天必须回到城市 $1$ 的状态
• 通过维护最优值矩阵确保路径可行性

算法特点

1. 时间复杂度：$O((5n)^3 \log T + k(5n)^2 \log T)$，高效处理 $T = 10^9$
2. 空间复杂度：$O((5n)^2)$，存储转移矩阵和预处理结果
3. 优化效果：将指数级问题转化为多项式复杂度

解决效果

该算法成功解决了大规模时间范围内的路径优化问题，通过矩阵快速幂和状态压缩技术，在保证正确性的同时实现了高效计算，能够处理 $10^9$ 量级的时间范围，并巧妙融入美食节的时间点约束。