传送门:http://acm.hdu.edu.cn/showproblem.php?pid=6071

题目大意：给你一个 含四个点的带权环。问你从 2点 走到 2点 的 权值>= k 的最短路.

(边权 <= 30000 , k <= 1e18)

题目思路:

这题的思维难点在于:如何表征出所有可能的路径情况.

类似同余最短路的思想: k如此大,但是边权很小,我们考虑将边权放入状态中..

问题一:如何确定剩余系X.   由于我们一定要回到2点.所以不妨选择一条 [与2相连的边w * 2] 作为剩余系.

问题二:合理性?

首先一点: 此过程中访问节点的顺序不重要.重要的是 每条边的边权的访问次数. 可以看出:路径的权值和本质上是一种线性组合.

那么对于任意一条合法访问路径和 G ,我们都可以将其划分到 2 * w 个 剩余系中去.

   ----联想带余除法.

最后求解答案时: 对于 剩余系 i ,  将答案补成 G 的结构即可.