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;
}