【BZOJ 4144】[AMPPZ2014] Petrol

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4144
神犇题解：http://www.cnblogs.com/Tunix/p/4593049.html

解题报告

随便想一想，这题似乎除了有加油站的点之外，其他点似乎完全可以不用考虑？
再仔细想一想的话，我们似乎只要求出任意两个有加油站的点的最短路，然后再做一个MST就可以了！

现在的问题就是如何求出任意两点的最短路了
我们考虑放宽一点条件，求出一些最短路径的集合 $\{ e \}$ ，使其能够凑出任意两点的最短路
现在考虑两点之间最短路的性质：

定义$blg(x)$表示离$x$最近的关键点
那么对于 $a \to b$ 最短路上，一定是前一部分$blg(x)=a$，后一部分$blg(x)=b$
于是我们就可以通过枚举原图中的一条边$(x_1,x_2)$并且判断$blg(x_1)$是否等于$blg(x_2)$来找到所有中途不经过加油站的最短路

如何证明呢？考虑反证法：如果中途有一个点$blg(y)=c$那么先从$a \to b \to c$一定不比$a \to b$劣
这是因为如果我们走到y点后绕道到c点去加油，回来的时候油量一定不少于从a点到y点的油量

这样我们就可以找到一个边集 $\{ \varepsilon \}$使得 $\{ e\} \subset \{ \varepsilon \}$
于是我们把$\{ \varepsilon \}$拿出来，做一个最小生成树，然后查询的时候，在树上倍增一下就可以啦！