CF1715E long way home

本题并不难。
观察一下数据范围 \(k\) 非常小，那么不难发现我们可以把跳这个操作做 \(k\) 遍即可。

跳操作的式子一看就很斜率优化 \((u-v)^2=u^2+v^2-2uv\) 直接李超树维护即可。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
	x = 0; char ch = getchar(); bool flg = 0;
	for (; !isdigit(ch); ch = getchar()) flg |= (ch == '-');
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	if (flg) x = -x;
	read(Ar...);	
}
inline char Getchar(){ char ch; for (ch = getchar(); !isalpha(ch); ch = getchar()); return ch;}
template <typename T> inline void write(T n){ char ch[60]; bool f = 1; int cnt = 0; if (n < 0) f = 0, n = -n; do{ch[++cnt] = char(n % 10 + 48); n /= 10; }while(n); if (f == 0) putchar('-'); for (; cnt; cnt--) putchar(ch[cnt]);}
template <typename T> inline void writeln(T n){write(n); putchar('\n');}
template <typename T> inline void writesp(T n){write(n); putchar(' ');}
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void readstr(string &s) { s = ""; static char c = getchar(); while (isspace(c)) c = getchar(); while (!isspace(c)) s = s + c, c = getchar();}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 1e5 + 10;
struct edge {
	int v, w, nxt;
} e[N << 1];

int cnt = 1, head[N], n, m, k;
inline void aedge(int u, int v, int w) {
	e[++cnt] = (edge) {v, w, head[u]};
	head[u] = cnt;
}

LL dis[N];
const LL INF = 1e18;
#define pii pair<LL, int>
#define fi first
#define se second
inline void dijkstra() {
	priority_queue< pii, vector< pii >, greater< pii > > q;
	U(i, 1, n) q.emplace(dis[i], i);
	while (!q.empty()) {
		pii x = q.top();
		q.pop();
		int u = x.se;
		if (dis[u] != x.fi) continue ;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v, w = e[i].w;
			if (dis[u] + w < dis[v]) 
				q.emplace(dis[v] = dis[u] + w, v);
		}
	}
}

struct Seg {
	LL k, b;
	Seg(){}
	Seg(LL k, LL b) : k(k), b(b) {}
} s[N];

inline LL w(int id, int pos) {
	return s[id].k * pos + s[id].b;
}

struct Segment_Tree {
	int t[N << 2];
	#define lson (pos << 1)
	#define rson (pos << 1 | 1)

	inline void clear() {
		memset(t, 0, sizeof t);
	}

	inline void modify(int pos, int l, int r, int cur) {
		int mid = l + r >> 1;
		if (w(t[pos], mid) > w(cur, mid)) 
			swap(t[pos], cur);
		if (l == r) return ;
		if (w(t[pos], l) <= w(cur, l) && w(t[pos], r) <= w(cur, r)) return ;
		if (s[cur].k > s[t[pos]].k) modify(lson, l, mid, cur);
		else modify(rson, mid + 1, r, cur);
	}

	inline LL query(int pos, int l, int r, int p) {
		if (l == r) 
			return w(t[pos], p);
		int mid = l + r >> 1;
		LL res = w(t[pos], p);
		if (p <= mid) chkmin(res, query(lson, l, mid, p));
		else chkmin(res, query(rson, mid + 1, r, p));
		return res;
	}
} sgt;

int main(){
	//FO("");
	s[0] = Seg(0, INF);
	read(n, m, k);
	U(i, 1, m) {
		int u, v, w;
		read(u, v, w);
		aedge(u, v, w);
		aedge(v, u, w);
	}

	U(i, 2, n) dis[i] = INF;
	dijkstra();
	U(i, 1, k) {
		sgt.clear();
		U(j, 1, n) {
			s[j] = Seg(-2 * j, (LL) j * j + dis[j]);
			sgt.modify(1, 1, n, j);
		}
		U(j, 1, n) chkmin(dis[j], sgt.query(1, 1, n, j) + (LL) j * j);
		dijkstra();
	}
	U(i, 1, n) writesp(dis[i]);
	return 0;
}