rt,本人此题最短路后三个点挂掉了,但是最长路能过.

@Deep_Kevin 大佬给的数据说明了在图不连通的时候,如果跑最短路应该在弱连通子图中去考虑.但为什么最长路能规避这一问题呢?

是不是因为最长路跑出来的解保证了非负性,所以从全局考虑和从子图考虑结果一样?

原帖地址:

https://www.luogu.com.cn/discuss/show/256016?page=1