如果保证了每条边恰好经过一定次数的话这个方法应该可行,一般不建议拿Dij跑负权单源最短路,不过有拿dij做的负权全源最短路O($n^2logn$)的做法
by tx774 @ 2023-10-23 15:20:38
你一定经过负权边仅一次,所以是对的。一般 dij 不能这样用是因为不知道会经过几条加过较大值的边。
by yinhee @ 2023-10-23 15:32:56