[Div1]「CodePlus 2018 4 月赛」最短路

[Div1]「CodePlus 2018 4 月赛」最短路
n \leq 100000,m \leq 500000的有向图,
两点之间还可以以a xor b的代价从ab,问st的最短路。
先两个点之间不走给定的边,最短路一定是直接ss到tt,
因为一个二进制的差异至少要被算一次。观察st的过程,
可以把这个过程完全等价地变成:一次只改一个二进制位,代价完全不变。
因此xor的边只用连nlog2(n)条,然后就无脑最短路了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注