2023 蓝桥杯热身赛

Problem P05. 异世界的地图(10分)

果冻有一份世界地图,上面标注了各魔法传送点及传送点两两间的传送路线,有一些路线是双向的、另外一些是单向的。如果传送路线是双向的,果冻可以从该路线的两点中任一点传送到另一点;如果传送路线是单向的,果冻只能从起点传送到终点。

由于极其特殊的气候,当前季节很长时间内恒定会出现一天雨天、一天晴天的循环交替。每次传送都需要消耗魔法。晴雨不同会影响魔法流,因此晴雨不同时,传送消耗的魔法也可能不同。

果冻听闻在某个传送点附近居住着名为禾枫的贤者,于是他打算前往拜访贤者。果冻当前在传送点 1 ,当天是晴天。从当天开始(含当天),果冻每天都可以使用至多一次传送。由于果冻的魔法量很低,他想要在到达目的地时总消耗最小,请算出最小消耗。

例如,假设有传送点间情况如下表,想前往传送点 5 ,最小消耗是 19

起点终点是否双向晴天消耗雨天消耗
13Y1020
35Y1022
21N12
32N102
24Y48
34Y3032
14Y3430
45Y153

假设有 n=1437 个传送点, m=4096 条传送路线。第 i 条传送路线的起点 u_i((1399i^2+u_{i-1}^2)\bmod n)+1 ,终点 v_i((1427i^2+v_{i-1}^2)\bmod n)+1 ,特别地,当计算得 u_i=v_i 时,令 u_i=(u_i\bmod m)+1。若 i 为奇数是双向传送路线;否则是单向传送路线。晴天消耗 x_ii 的正因数之和加 x_{i-1} 后对 m 取模后再加一,雨天消耗 y_ii 的不大于 m 的所有正倍数之和加 y_{i-1} 后对 m 取模后再加一。其中 u_0=v_0=x_0=y_0=0 ,注意 1 是所有数的因数;所有数的因数和倍数包含其自身。求到传送点 n 的最小消耗。

假设你的程序生成的数据前五条传送路径如下所示,那么你的数据生成可能是正确的:

起点终点是否双向晴天消耗雨天消耗
14001428Y22049
121842N62
199238Y113416
195442N191369
11511120Y26960

输入

输出

你的答案

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 8
通过 4