有大佬解答吗
by 06ray @ 2018-07-06 08:35:37
@[陆麟瑞666](/space/show?uid=42443) 建反的负数边吧
by YLWang @ 2018-07-06 08:42:33
@[陆麟瑞666](/space/show?uid=42443) 三角形不等式再去看看。。
by moye到碗里来 @ 2018-07-06 11:32:04
@[陆麟瑞666](/space/show?uid=42443) 最短路是基于松弛的，松弛是基于三角形不等式的，弄懂了就好
by moye到碗里来 @ 2018-07-06 11:50:08
( %%% $llr$ )
根据最短路性质：
$Dis(i) <= Dis(j) + edge(j, i)$.
情况1：$Xi - Xj <= Wk$，把$Xj$移到右边并类比上式，就从$j$到$i$连一条权是$Wk$的边.
情况2：$Xi - Xj >= Wk$，两边乘以$-1$，转换成$Xj - Xi <= -Wk$，转化为情况1，
于是$i$到$j$连一条权为$-Wk$的边.
情况3：$Xi - Xj == Wk$ 就上面两个都做。“大于等于”$and$“小于等于”相当于“等于”.
图中有负环时无解
大概就酱紫吧 $QAQ$
（PS：水平不高，仅供参考
by hongzy @ 2018-07-17 20:54:04
@[陆麟瑞666](/space/show?uid=42443)
by hongzy @ 2018-07-18 17:01:18
@[hongzy](/space/show?uid=20375) 蟹蟹巨佬，orz
by 06ray @ 2018-07-18 17:02:35