题解
注意到 \(k\) 是一个很小的数，我们考虑分层图是否可做，这时航线有 \(n^2\) 条，我们可能会建出 \((k+1)m+kn^2\) 条边，空间会炸掉，然而单单从分层图的角度来优化，是困难的。
对于 \(m=0\) 的情况。考虑 \(\text{dp}\)，定义 \(dp_{i,j}\) 表示乘坐不超过 \(i\) 次航班到达 \(j\) 的最小花费。那么有如下转移方程：
\[dp_{i,j}=\min({\min_{1 \le t \le n}{dp_{i-1,t}+(j-t)^2}},dp_{i-1,j}) \]暴力递推的复杂度是 \(O(kn^2)\) 的，炸了。我们转化一下 \(\text{DP}\) 的转移方程：
\[dp_{i,j}=\min({\min_{1 \le t \le n}(-2jt+dp_{i-1,t}+t^2)+j^2},dp_{i-1,j}) \]我们定义出 \(n\) 条线段，对于第 \(i\) 条线段，其解析式为：
\[y=-2tx+dp_{i-1,t}+t^2(1\le x \le n) \]那么我们就是要求直线 \(x=j\) 与这 \(n\) 条线段的交点中纵坐标的最小值，可使用李超线段树维护，注意到，由于插入的线段的定义域都是相同的，我们没有拆分区间的必要，于是插入一条线段的复杂度是 \(O(\log n)\) 的，总复杂度为 \(O(kn\log n)\)。
对于 \(m>0\) 的情况。保持 \(dp_{i,j}\) 的定义不变，那么在做完上述转移之后，我们还有如下转移式：
\[dp_{i,j}=\min_{(t,j)\in E}dp_{i,t}+w(t,j) \]其中 \(E\) 是原图边集，这里无后效性不能保证，但是显然可用 \(\text{Dijkstra}\) 算法更新。这一部分的时间复杂度仍然是 \(O(kn\log n)\)。那么，我们就在 \(O(kn\log n)\) 的时间内解决了问题。
代码实现上，要注意的是：1.转移的第一维只涉及两个阶段，可用滚动数组减小空间常数。2.在用 \(\text{Dijkstra}\) 算法更新时，\(dp_{i,j}\) 是有初值的，可以看作有一条边 \((1,j,dp_{i,j})\)，所以要先把这 \(n\) 条边入队。3.对于 \(dp_{0,j}\)，这个相当于原图最短路，还是有意义的，要求解。
AC code
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
const int inf=1e15;
int n,m,k;
int ver[N],edge[N],head[N],Next[N],d[N],D[N],vis[N],tot,u,v,w;
int rt,sz,ans;
priority_queue<pair<int,int> >q;
struct Line {
int k,b;
}a[N];
struct node {
int ls,rs,mx;
}t[N<<2];
bool check(int i,int j,int x) {
if(a[i].k*x+a[i].b-a[j].k*x-a[j].b>0) return false;
return true;
}
void Insert(int &p,int L,int R,int pos) {
if(!p) p=++sz;
if(check(pos,t[p].mx,L)&&check(pos,t[p].mx,R)) {
t[p].mx=pos;
return;
}
if(!check(pos,t[p].mx,L)&&!check(pos,t[p].mx,R)) return;
int mid=L+R>>1;
if(check(pos,t[p].mx,mid)) swap(pos,t[p].mx);
if(check(pos,t[p].mx,L)) Insert(t[p].ls,L,mid,pos);
if(check(pos,t[p].mx,R)) Insert(t[p].rs,mid+1,R,pos);
}
void query(int p,int L,int R,int x) {
if(!p) return;
if(check(t[p].mx,ans,x)) ans=t[p].mx;
if(L==R) return;
int mid=L+R>>1;
if(x<=mid) query(t[p].ls,L,mid,x);
else query(t[p].rs,mid+1,R,x);
}
void add(int x,int y,int z) {
ver[++tot]=y;
edge[tot]=z;
Next[tot]=head[x];
head[x]=tot;
}
void dijkstra() {
for(int i=1;i<=n;i++) {
vis[i]=0;
q.push(make_pair(-d[i],i));
}
while(!q.empty()) {
int x=q.top().second;
q.pop();
if(vis[x]) continue;
vis[x]=1;
for(int i=head[x];i;i=Next[i]) {
int y=ver[i],z=edge[i];
if(d[y]>d[x]+z) {
d[y]=d[x]+z;
q.push(make_pair(-d[y],y));
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=m;i++) {
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
for(int i=1;i<=n;i++) d[i]=inf;
d[1]=0;
dijkstra();
a[0].k=0,a[0].b=inf;
for(int i=1;i<=k;i++) {
for(int j=1;j<=n;j++) {
a[j].k=-2*j,a[j].b=d[j]+j*j;
Insert(rt,1,n,j);
}
for(int j=1;j<=n;j++) {
ans=0;
query(rt,1,n,j);
D[j]=min(d[j],-2*ans*j+d[ans]+ans*ans+j*j);
}
for(int j=1;j<=n;j++) d[j]=D[j];
dijkstra();
}
for(int i=1;i<=n;i++) cout<<d[i]<<" ";
return 0;
}