@[JQ6561](/user/158058)
您的题面描述可能不太清晰，这玩意直接上spfa不就好了
by 太阳起晚了呢 @ 2021-11-16 18:16:05
点数1e5,边数1e7
by JQ6561 @ 2021-11-16 18:36:06
图有环，spfa为什么能做
by JQ6561 @ 2021-11-16 18:37:39
这是np的吧。
你考虑如果你能做这道题，那么你就可以多项式时间求两两点的最长简单路径。
那么给你一个图，你把所有边权都置为1，两两点最长路如果是 n-1，就有哈密顿路径，相当于你可以多项式判断图是否有哈密顿路。
by eexyz @ 2021-11-17 18:32:26
@[JQ6561](/user/158058)
by eexyz @ 2021-11-17 18:33:58
我为什么看不懂题目描述（
by OIforJoy @ 2021-11-18 11:11:36
@[OIforJoy](/user/63964) orz
by eexyz @ 2021-11-19 13:10:43