CWOI S C0319 B 小黄鸭和最短路

题意

U2FsdGVkX19M0E9ervL04/geQZ7BNe+LkSFZFRsNAinzYdaGU6jwRo7JYASn1uH0
wYLIlBH6SnQACiFivzdNbBM/zg4Dd7SRzslpci7/WusezpfqqdYqaiJeLdIyp1WG
GPaz3eCiQFH4awCfWEMGUTWZfidIE7sfCY/V5DRUOCoFFRmdDe7jCIQ4lAKgBTLr
AjbmQfd+vrl32bWkBd3lWOoYB2GMhboVcEZ83TUf+Xs=

解析

假设当前时间为 p，考虑如何求出从 p 后第一个被清空的位置。这个显然可以二分， check 的时候就直接暴力跑 dijkstra。但是这样的复杂度是假的，假设总共清空次数为 k，即需要进行 k 次这样的二分，复杂度是 $O(k n\log n \log q)$，而 k 很容易能卡到 q。

我们使用倍增优化这个过程。先尝试 p 后 $2^0$ 条边，$2^1$ 条，$2^2$ 条，……。如果在 $2^x$ 条边的时候发现最短路小于等于 T 了，而 $2^{x-1}$ 是没有，则在 $[2^{x-1}, 2^x]$ 这个区间二分。这样的复杂度是正确的。假设这一段的长度是 L，则倍增的复杂度是 $O(L \log n \log L)$，而二分的复杂度也是是 $O(L \log n \log L)$（实现 dijkstra 时只考虑相关的边），由于 $\sum L = q$，所以复杂度就正确了。

#include <algorithm>
#include <iostream>
#include <queue>
#include <limits>
#include <tuple>
#include <vector>

constexpr int INF = std::numeric_limits<int>::max() / 2;

int main()
{
	int n, m, T;
	std::cin >> n >> m >> T;

	std::vector<std::tuple<int, int, int>> edges;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		std::cin >> u >> v >> w;
		u--;
		v--;
		edges.emplace_back(u, v, w);
	}

	auto dijkstra = [&edges, n](int begin, int end)
	{
		static std::vector<std::vector<std::pair<int, int>>> adj(n);
		static std::vector<int> dis(n, INF);
		static std::vector<bool> vis(n);

		for (int i = begin; i < end && i < (int)edges.size(); i++) {
			auto [u, v, w] = edges[i];
			adj[u].emplace_back(v, w);
			adj[v].emplace_back(u, w);
		}

		dis[0] = 0;
		std::priority_queue<std::pair<int, int>,
			std::vector<std::pair<int, int>>,
			std::greater<>> q;
		q.emplace(0, 0);
		while (!q.empty()) {
			auto [_, u] = q.top();
			q.pop();
			if (vis[u]) continue;
			vis[u] = true;
			for (auto [v, w] : adj[u]) {
				if (dis[v] > dis[u] + w) {
					dis[v] = dis[u] + w;
					q.emplace(dis[v], v);
				}
			}
		}

		auto res = dis[n - 1];
		for (int i = begin; i < end && i < (int)edges.size(); i++) {
			auto [u, v, _] = edges[i];
			adj[u].clear();
			adj[v].clear();
			dis[u] = dis[v] = INF;
			vis[u] = vis[v] = false;
		}
		vis[0] = false;

		// std::cerr << begin << " " << end << " " << res << std::endl;

		return res;
	};

	std::vector<int> time;
	{
		int p = 0;
		bool flag = true;
		while (flag) {
			int t = 1;
			while (true) {
				if (dijkstra(p, p + t) <= T) {
					break;
				} else if (p + t >= m) {
					flag = false;
					break;
				}
				t *= 2;
			}
			if (!flag) break;
			int l = p + t / 2, r = p + t;
			while (l < r) {
				int mid = l + (r - l) / 2;
				if (dijkstra(p, mid) <= T) {
					r = mid;
				} else {
					l = mid + 1;
				}
			}
			time.emplace_back(r);
			p = r;
		}
	}

	std::cout << time.size() << std::endl;
	for (auto i : time) std::cout << i << " ";
	std::cout << std::endl;
}