link：https://codeforces.com/contest/1715/problem/E
有 \(n\) 座城市，城市间有 \(m\) 条双向道路，通过第 \(i\) 条道路需要花费 \(w_i\) 的时间，任意两个城市之间都有航班，乘坐城市 \(u\) 和 \(v\) 之间的航班需要花费 \((u-v)^2\) 的时间。
现在请对于任意城市 \(i(1 \le i \le n)\)，求出从城市 \(1\) 出发，到达城市 \(i\) 所需要的最短时间，注意从城市 \(1\) 到 \(i\) 的过程中最多乘坐 \(k\) 次航班。
\(2 \leq n \leq 10^{5}\) , \(1 \leq m \leq 10^{5}\) , \(1 \leq k \leq 20\)
看到花费 \(=u^2 +v^2 -2uv\) 就感觉DNA动了，\(k\leq 20\) 也肯定是有用的，一个自然的想法就是做dp：\(f(i,j)\) 表示到 \(i\) 号点，使用了 \(j\) 次飞行的最小时间，那么 \(f(u,j)\) 可以是在 \(j-1\) 轮次到达某个点 \(v\) ，再从 \(v\to u\) 花费 \(u^2 +v^2 -2uv\) 的代价转移，转移式子 \(f(u,j)=u^2 +\min_v f(v,j-1)+v^2 -2uv\) 显然具有决策单调性，看成是若干条直线求上凸壳。
但也可以是在这一次之后又在图上走了一段，这部分就很麻烦了，可能需要枚举的点对很多，赛时在这里想了很久才意识到：为什么不每次转移完DP再跑一次dijkstra呢？dp求出了强制最后一下通过航班到达的最短时间，那就从 \(1\) 到每个点连上这样的边，然后再跑一次最短路就行。
（注：不能每次dp完都加上 \(O(n)\) 条边，这样就变成 \(O(nk^2 \log n)\) 了…应该记录下额外加的这 \(n-1\) 条边的编号，直接每次修改他们）
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int N=1e5+5;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
struct state{
int x;
ll w;
state(int x,ll w):x(x),w(w){}
bool operator <(const state &rhs)const{
return w>rhs.w;
}
};
int n,m,k;
vector<vector<pair<int,ll>>> G;
vector<ll> dijkstra(int st){
vector<ll> dis(n+1);
dis.assign(n+1,INF);
priority_queue<state> Q;
Q.emplace(st,dis[st]=0);
while(!Q.empty()){
auto [x,d]=Q.top();
Q.pop();
if(dis[x]!=d)continue;
for(auto [v,w]:G[x])if(dis[v]>dis[x]+w)
Q.emplace(v,dis[v]=dis[x]+w);
}
return dis;
}
struct Line{
ll k,b;
__int128 calc(int x){return (__int128)k*x+b;}
};
int main(){
fastio;
cin>>n>>m>>k;
G=vector<vector<pair<int,ll>>>(n+1);
rep(i,1,m){
int u,v,w;
cin>>u>>v>>w;
G[u].push_back({v,w});
G[v].push_back({u,w});
}
int st=G[1].size();
rep(i,2,n)G[1].push_back({i,INF});//i:G[1][st+i-2],
rep(tc,1,k){
auto d=dijkstra(1);
vector<ll> f(n+1);
vector<Line> S;
rep(i,1,n){
ll b3=(ll)i*i+d[i],k3=-2*i;
while(S.size()>=2){
int sz=S.size();
auto [k1,b1]=S[sz-2];
auto [k2,b2]=S[sz-1];
if((__int128)(b2-b1)*k1+(__int128)b1*(k1-k2)>(__int128)(b2-b1)*k3+(__int128)b3*(k1-k2))
S.pop_back();
else break;
}
S.push_back((Line){k3,b3});
}
int sz=S.size(),cur=0;
rep(i,1,n){
while(cur+1<=sz-1){
auto v1=S[cur].calc(i),v2=S[cur+1].calc(i);
if(v1>v2)cur++;
else break;
}
f[i]=(ll)i*i+S[cur].calc(i);
}
rep(i,2,n)G[1][st+i-2].second=min(G[1][st+i-2].second,f[i]);
}
auto d=dijkstra(1);
rep(i,1,n)cout<<d[i]<<' ';
return 0;
}