CodeChef Sum of distances(分治)
有一排点，每个点 i 向 $i + 1, i + 2, i + 3$ 分别连价值为 $a_i,b_i,c_i$ 的有向边，问两两间最短路之和
CodeChef Sum of distances(分治)
题目大意
有一排点，每个点 i 向 \(i + 1, i + 2, i + 3\) 分别连价值为 \(a_i,b_i,c_i\) 的有向边，问两两间最短路之和
数据范围
\(1 \le n \le 10^5\)
解题思路
这种题已经从新颖变成套路了（唉）
考虑分治，很容易发现如果断掉连续的三个点那么图就不再联通，我们从中间找三个点，然后分别向两边跑最短路，设点 i 到三点最短距离为 \(x_1,x_2,x_3\)，三点到 j 最短距离为 \(y_1,y_2,y_3\)
那么对答案的贡献为 \(\min(x_1+y_1,x_2+y_2,x_3+y_3)\)
考虑 \(x_1+y_1\) 最小，有
\[x_1+y_1 \le x_2+y_2,x_1+y_1 \le x_3+y_3\\
x_1-x_2 \le y_2-y_1,x_1-x_3 \le y_3-y_1
\]
x_1-x_2 \le y_2-y_1,x_1-x_3 \le y_3-y_1
\]
简单的二维偏序问题，但实现起来较为复杂，考虑 \(x_2+y_2\) 时注意小于等于号和小于号的情况
代码先咕了
版权声明：本文为Hs-black原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。