CF843D

Dijkstra 的好题。

题意：给定一张图，可能询问某点到 1 的最短距离或是给 $c$ 条边的边权加 1。$n, m\leq 10 ^ 5, q\leq 2000, \sum c\leq 10 ^ 6$。

直接考虑朴素的 Dijkstra，每次我们加边的时候，都暴力重构长度。时间复杂度 $O(mq\log n)$，很卡。标算都卡的很，这还能过？

另一种方法是用 SPFA 代替，时间复杂度 $O(kmq)$，好像被构造卡了。

10 s 的时间，看样子不是什么特别优的算法，应该是 $O(mq)$。

似乎只有 BFS 可以做到这个复杂度，01 双端队列似乎可以解决！

但是我们没有考虑原来的边的边权，这个显然是有问题的，因为对于边权非 1 的情况会处理错误。那么有什么方法呢？

考虑 Dijkstra 的算法流程：

1. 找到当前未扩展的点中，距离起点最近的点。
2. 松弛其他点到起点的距离。

在标准的 Dijkstra 算法中，我们使用了一个堆实时维护。我们是否可以找到另外的替代呢？直接考虑最暴力的桶，于是我们得到了一个 $O(m + W)$ 的做法，其中 $W$ 是指最短路的值域范围。

每次加 $c$ 条边的边权时，到其他所有点的距离变化一定不超过 $\min\{c, n - 1\}$（最短路不超过 $n - 1$ 条边），这启示我们可以使用桶 - Dijkstra 的算法来计算增量。

但是在一般的认知中，是没有办法求最短路的增量的。可以考虑类似 Johnson 全源最短路的做法，我们设置一条边的新权值为 $e(u, v)’ = e(u, v) + dis(u) - dis(v)$。类似 Johnson 的证明，我们三角不等式易得边权仍然是非负的。而我们走到一个点的时候，他的势能加上他的新图上的距离就是原图上的最短路。而新图的距离是好求的，于是我们可以得到单次 $O(m + W) = O(m)$ 的做法了。总时间复杂度 $O(m\log m + mq)$（开始必须跑一遍 Dijkstra

注意仍然比较卡常，注意实现细节的错误可能导致 TLE。放一个代码。

std::queue<int> q[N];
void bfs(int Lim = n - 1)
{
	for (int i = 1; i <= Lim; ++ i)
		while (!q[i].empty()) q[i].pop();
	for (int i = 1; i <= n; ++ i) now[i] = n;
	q[0].push(1), now[1] = 0;
	int mx = 0;
	for (int l = 0, x; l <= mx; ++ l)
		while (!q[l].empty()) {
			x = q[l].front();
			q[l].pop();
			if (now[x] < l) continue;
			for (auto &[i, v] : g[x])
				if (chkmin(now[v], int(now[x] + w[i] + d[x] - d[e[i]])) && now[v] <= Lim)
					q[now[v]].push(v), chkmax(mx, now[v]);
		}
	for (int i = 1; i <= n; ++ i)
		if (d[i] < (INF >> 1)) d[i] += now[i];
}