这个 \(k\) 非常小，所以我们考虑全部依次飞这 \(k\) 次行程。
这个飞来飞去是一个平方的形式，我们考虑优化这一形式。
首先我们知道从 \(u\) 飞到 \(v\) 后就可以这样做：
\[dis_u + (u -v)^2 \to dis_v
\]
\[dis_u + u^2 + v^2 - 2uv \to dis_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;
}