P1852

一个粗略的想法是对于所有状态 \((a,b,c)\) 之间连边，求出图之后跑最短路。 首先钦定 \(a\le b\le c\), 考虑转移有哪些情况：要么从两边到中间距离小的一个往中间跳缩小范围，要么中间往两边跳扩大范围。我们定义第一种到的状态为父亲，第二种到的状态为左右儿子，不难发现整个图是一棵二 ......

#include <iostream> #include <vector> #include <algorithm> #include <numeric> using namespace std; const double EPS = 1e-8; int main() { int n, k; cin ......