差分约束总结
给定若干条件
比如 \(a - b \le c\)
这样的话从b到a连一条边权为c的边。
最后要求\(x-y\)的最大值直接跑x到y的最短路即可。
同理 也可以从a到b连一条边权为-c的边,最后跑最长路。
注意能不能跑dijkstra
给定若干条件
比如 \(a - b \le c\)
这样的话从b到a连一条边权为c的边。
最后要求\(x-y\)的最大值直接跑x到y的最短路即可。
同理 也可以从a到b连一条边权为-c的边,最后跑最长路。
注意能不能跑dijkstra