题意给出一个 $N$ 点 $M$ 边的有向图，以及 $K$ 个感兴趣的点，求感兴趣的点两两之间最短路的最小值。$N\le 100000 \ , \ M\le 500000$ 。题解如果建立原点和汇点，把 $K$ 个点分成两组，分别与原点汇点相连，再从原点开始跑到汇点的最短路就是最小值。但这样显然无法涵盖所有情况。所以枚举二进制位，把当前位为 $1$ 的加入第一组，其它的放入第二组。因为两个数...
题意给出一个 $N$ 点 $M$ 边的有向图，并给出最短路径。依次删掉最短路上的每条边，求删边后最短路长度。$N\le 10^5 \ , \ M\le 2\times 10^5$ 。题解朴素的做法可以每删一条边就跑一次 $\text{Spfa}$ ，但这样显然会爆。可以发现不需要每次都更新所有点的最短路。如果删除 $(u,v)$ ，那么最短路一定是 $$1\rightarrow x\righ...
题意给出一个 $N$ 点 $M$ 边的有向图，要从 $1\rightarrow D$ 。每条边上有限速，如果限速为 $0$ 则需要按照上一条边的速度走。求最短用时。$N\le 150$ 。题解给朴素的最短路加上一维，用 $dis[x][s]$ 表示在节点 $x$ ，当前速度为 $s$ 的最短用时。然后跑 $\text{Spfa}$ 即可。tips: 对 double 进行 memset 时最...
题意给出一个 $N$ 点无向图，至少有两个连通块。求连接两个连通块的方案，使得新连通块的直径最小。$N\le 150$ 。题解先用 $\text{Floyd}$ 跑最短路，然后可以算出从每个点出发的最远距离，然后枚举两个不连通的点连上即可得到答案。但有可能出现连接的两个点不是直径两端的情况，这时原来连通块的直径就是这个新连通块的直径，所以需要取最大值。#include<bits/std...