小花的题解中方式一建图需要注意,先给所有区间按照左端点进行排序,否则会有这组hack:
3 1 -4 -2 -6 -4 -3 0
正确输出:5
错误输出:7
模拟一下就容易发现问题所在了。
以及 S' 向所有区间左端点连边的时候费用为 0,不是 -1。