【CF1715E】Long Way Home

这个 \(k\) 非常小，所以我们考虑全部依次飞这 \(k\) 次行程。

这个飞来飞去是一个平方的形式，我们考虑优化这一形式。

首先我们知道从 \(u\) 飞到 \(v\) 后就可以这样做：

这里我们可以钦定 \(u < v\)，然后斜率优化做两遍，但是感觉不如直接写李超树维护即可。

但是更新后的点可以在走一些路，然后就会更新到一些城市的答案，所以考虑先进行算完斜率优化，再跑一遍 dijkstra 即可。

时间复杂度 \(kn\log (n+ m)\)。

代码：

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ls u << 1
#define rs u << 1 | 1

const int N = 1e5 + 5, MOD = 998244353;

struct NODE {
	int u, w;
	bool operator < (const NODE & x) const {
		return w > x.w;
	} 
};

priority_queue <NODE> q;
vector <pair<int, int>> e[N];

struct line {
	int k, b;
	line (int k = 0, int b = 1e16) : k(k), b(b) {}	
	inline int val (int x) { return k * x + b; }
} ;

struct lichaotree {
	line t[N << 2];
	inline void clear (int u, int l, int r) {
		if (l == r || t[u].k == 0) return ;
		t[u].k = 0, t[u].b = 1e18; 
		int mid = (l + r) >> 1;
		clear(ls, l, mid), clear(rs, mid + 1, r);
	}
	inline void modify (int u, int l, int r, line x) {
		if (l == r) {
			if (x.val(l) < t[u].val(l)) t[u] = x; 
			return ;
		} int mid = (l + r) >> 1;
		if (x.val(mid) < t[u].val(mid)) swap(x, t[u]);
		if (x.val(l) < t[u].val(l)) modify(ls, l, mid, x);
		if (x.val(r) < t[u].val(r)) modify(rs, mid + 1, r, x);
	}
	inline int query (int u, int l, int r, int pos) {
		int res = t[u].val(pos), mid = (l + r) >> 1;
		if (l == r) return res;
		if (pos <= mid) return min(res, query(ls, l, mid, pos));
		else return min(res, query(rs, mid + 1, r, pos));
	}
} lct;

int n, m, k;
int dist[N];

inline void dijkstra () {
	for (int i = 1; i <= n; i ++) q.push({i, dist[i]});
	while (! q.empty()) {
		NODE t = q.top(); q.pop();
		int u = t.u, d = t.w;
		if (d != dist[u]) continue ;
		for (auto & [v, w] : e[u])
			if (dist[v] > d + w) dist[v] = d + w, q.push({v, dist[v]});
	}
}

signed main () {
	ios :: sync_with_stdio(0);
	cin >> n >> m >> k;
	for (int i = 1, u, v, w; i <= m; i ++) {
		cin >> u >> v >> w;
		e[u].emplace_back(v, w), e[v].emplace_back(u, w);
	}
	for (int i = 2; i <= n; i ++) dist[i] = 1e16;
	dijkstra();
	for (int i = 1; i <= k; i ++) {
		lct.clear(1, 1, n);
		for (int j = 1; j <= n; j ++)
			lct.modify(1, 1, n, line(-2 * j, j * j + dist[j]));
		for (int j = 1; j <= n; j ++)
			dist[j] = min(dist[j], lct.query(1, 1, n, j) + j * j);
		dijkstra();
	}
	for (int i = 1; i <= n; i ++) cout << dist[i] << " ";
	return 0;
}