Loading...
Preface 第三次做这题了... 顺便当成博客迁移了。下面的题解是高二上的时候写的，在 Hexo 的 blog，这里直接进行迁移：https://gyrojeff.moe/2020/09/18/P4568-JLOI2011-%E9%A3%9E%E8%A1%8C%E8%B7%AF%E7%BA%BF-%E5%88%86%E5%B1%82%E5%9B%BE%E6%9C%80%E7%9F%AD%...
Preface 之前做过很多最短路的题，基本上都使用堆优化的dijkstra，包括建立分层图等高级建图方法，但是一直没有系统地写过dijkstra本身是怎么推导的。今天重点想要形象地写一下以前金牌教练以前教最短路的方法。 单源最短路问题 我们先来简单地描述一下最短路问题：对于一张图 $G$，我们欲求起点 $S$ 到各点地最短距离。 要解决这个问题，我们不妨来先了解一下图论基本方程：对于每个点...