众所周知,不开long long见祖宗，如果你Wa on 8且和我一样一身反骨把斜率比较写成乘法的形式，那么你的long long被这组数据卡炸了

以下为警戒代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;
struct edge{
    int v,w;
};
vector<edge> bian[N];
struct node{
    int dis,idx;
    friend bool operator<(node a,node b){
        return a.dis>b.dis;
    }
};
priority_queue<node> pque;
bool vis[N];
int dis[N];
void dij(){
    memset(vis,0,sizeof(vis));
    pque.push((node) {dis[1],1});
    while(!pque.empty()){
        node no = pque.top();
        pque.pop();
        if(vis[no.idx]){
            continue;
        }
        vis[no.idx] = true;
        for(edge e : bian[no.idx]){
            if(dis[e.v] > dis[no.idx]+e.w){
                dis[e.v] = dis[no.idx]+e.w;
                pque.push((node) {dis[no.idx]+e.w,e.v});
            }
        }
    }

}
deque<int> que;
int f[N],X[N],Y[N];
signed main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i = 1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        bian[u].push_back((edge){v,w});
        bian[v].push_back((edge){u,w});
    }
    memset(dis,0x3f,sizeof(dis));
    dis[1] = 0;
    dij();
/*
dp[i][j] = min(dp[i][j],dp[x][j-1]+(i-x)*(i-x))
dp[i][j] -i*i= dp[x][j-1]+x*x -2*i*x;
b = dp[i][j] - i*i
y = dp[x][j-1] + x*x
k = +2i
x = x;
*/
 
    for(int b = 1;b<=k;b++){
        que.clear();
        for(int i = 1;i<=n;i++){
            f[i] = dis[i];
        }
        for(int i = 1;i<=n;i++){
            X[i] = i;
            Y[i] = f[i] + i*i;
            while(que.size()>1 && (Y[que[que.size()-1]] - Y[que[que.size()-2]])*(X[i] - X[que[que.size()-1]]) > (Y[i] - Y[que[que.size()-1]])*(X[que[que.size()-1]] - X[que[que.size()-2]])){
                que.pop_back();
            }
            que.push_back(i);
        }
        for(int i = 1;i<=n;i++){
            while(que.size()>1 && (Y[que[0]] - Y[que[1]]) > 2*i*(X[que[0]] - X[que[1]])){
                que.pop_front();
            }
            int x = que.front();
            if(!x){
                continue;
            }
            if(f[i] > f[x] + (i - x)*(i - x)){
                dis[i] = f[x] + (i - x)*(i - x);
                pque.push((node){dis[i],i});
            }
        }
        dij();
    }
    for(int i = 1;i<=n;i++){
        cout<<dis[i]<<' ';
    }
}

神仙错法硬控我一下午。。。。