我之前一直记的迪杰斯特拉的翻译导致我把 dijkstra 写成了 dijstra 或者 dijskra…… 我以后叫她迪杰克斯歘！ dijkstra 是用来在有向图或者无向图中寻找任意两个点的最小距离的算法。但是无法处理带负环的图和求最长路。 dijkstra 的核心思想是由已找到的最短路的点集每次扩展一个点的最短路。 dis 数组代表由起点到其他点的最短路，初始化其为 \(I...

P5471- K-D tree优化建图-弹跳 优化建图是一种思想。 题意 有\(n\)个城市分布在小鸟岛上，有\(m\)个弹弓分布在这些城市里。因为弹弓体积大，固定麻烦，所以每个弹弓只能把小鸟弹飞到一块固定的矩形范围内的城市，同时小鸟会在空中滞留\(t_i\)的时间。闪电黄的家在1号城市，追求速度的它想知道，若只使用弹弓出行，它从家到其他所有城市的最短时间花费是多少。 抱歉魔...

因为是单向边，牛儿来回的路径长度并不相同，所以需要用两次 dijkstra，一次正向从 \(x\) 开始 dijkstra，再将边全部反向存再来一次。 因为是板子题比较良心 \(n\) 比较小，我们就可以用矩阵来存储啦。如果 \(n\) 比较大的话，我的想法是再造一个图，同时反向存边。内存可能占用比较大但是想起来简单。 代码很短。 12345678910111213141516...