题目 CF1715E - Long Way Home

输入样例:
5 7 2
4 2 244918642
4 3 102485779
1 5 85773280
3 4 2210803
2 3 802765861
3 4 469291723
2 4 68798746

//错误输出代码
#include<bits/stdc++.h>
using namespace std;
typedef __int128 Int;
int n,m,k;
Int value[100005];
Int dis[100005],vis[100005];
int head[100005],ver[200005],nxt[200005],len[200005],num=2;
void write(Int x){
	if(x>9)write(x/10);
	putchar(x%10^48);
}
void add(int u,int v,int w){
	ver[num]=v,len[num]=w,nxt[num]=head[u],head[u]=num++;
	ver[num]=u,len[num]=w,nxt[num]=head[v],head[v]=num++;
}
void dijkstra(int op){
	priority_queue< pair<Int,int> > Q;
	if(op){
		memset(dis,0x3f,sizeof(dis));
		memset(vis,0,sizeof(vis));
		dis[1]=0;
		Q.push({0,1});
	}
	else{
		memset(vis,0,sizeof(vis));		
		for(int i=1;i<=n;i++)Q.push(make_pair(-dis[i],i));	
	}
	while(Q.size()){
		int u=Q.top().second;
		Q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u],v;i;i=nxt[i])
			if(dis[v=ver[i]]>dis[u]+len[i]){
				dis[v]=dis[u]+len[i];
				Q.push({-dis[v],v});
			}
	}
}
int que[100005],l,r;
#define getx(i) ((Int)i*2)
Int gety(int i){return value[i]+(Int)i*i;}
Int getk(int i){return i;}
void Dynamic_programing(){
	for(int i=1;i<=n;i++)value[i]=dis[i];
	que[l=r=1]=1;
	for(int i=2;i<=n;i++){
		while(l<r&&( gety(que[r])-gety(que[r-1]) )*( getx(i)-getx(que[r]) )>=( gety(i)-gety(que[r]) )*( getx(que[r])-getx(que[r-1]) ))r--;
    	que[++r]=i;
	}    
	for(int i=1;i<=n;i++){
    	int L=l,R=r;
        while(L<R){
            int M=(L+R)>>1;
            if(( gety(que[M+1])-gety(que[M]) )<=getk(i)*( getx(que[M+1])-getx(que[M]) ))L=M+1;
            else R=M;
        }
    	int j=que[L];
    	dis[i]=min(dis[i],value[j] + Int(i-j)*(i-j));
	}
	/*
	ans-i*i+2*i*j=value[j]+j*j
	*/
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	dijkstra(1);
	for(int i=1;i<=k;i++){
		Dynamic_programing();
		dijkstra(0);
	}
	for(int i=1;i<=n;i++)write(dis[i]),printf(" ");
	puts("");
	return 0;
}

输出：
0 1 4 9 16 

//正确输出代码
#include<bits/stdc++.h>
using namespace std;
typedef __int128 Int;
int n,m,k;
Int value[100005];
Int dis[100005],vis[100005];
int head[100005],ver[200005],nxt[200005],len[200005],num=2;
void write(Int x){
	if(x>9)write(x/10);
	putchar(x%10^48);
}
void add(int u,int v,int w){
	ver[num]=v,len[num]=w,nxt[num]=head[u],head[u]=num++;
	ver[num]=u,len[num]=w,nxt[num]=head[v],head[v]=num++;
}
void dijkstra(int op){
	priority_queue< pair<Int,int> > Q;
	if(op){
		memset(dis,0x3f,sizeof(dis));
		memset(vis,0,sizeof(vis));
		dis[1]=0;
		Q.push({0,1});
	}
	else{
		memset(vis,0,sizeof(vis));		
		for(int i=1;i<=n;i++)Q.push(make_pair(-dis[i],i));	
	}
	while(Q.size()){
		int u=Q.top().second;
		Q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u],v;i;i=nxt[i])
			if(dis[v=ver[i]]>dis[u]+len[i]){
				dis[v]=dis[u]+len[i];
				Q.push({-dis[v],v});
			}
	}
}
int que[100005],l,r;
#define getx(i) (i*2)
Int gety(int i){return value[i]+(Int)i*i;}
Int getk(int i){return i;}
void Dynamic_programing(){
	for(int i=1;i<=n;i++)value[i]=dis[i];
	que[l=r=1]=1;
	for(int i=2;i<=n;i++){
		while(l<r&&( gety(que[r])-gety(que[r-1]) )*( getx(i)-getx(que[r]) )>=( gety(i)-gety(que[r]) )*( getx(que[r])-getx(que[r-1]) ))r--;
    	que[++r]=i;
	}    
	for(int i=1;i<=n;i++){
    	int L=l,R=r;
        while(L<R){
            int M=(L+R)>>1;
            if(( gety(que[M+1])-gety(que[M]) )<=getk(i)*( getx(que[M+1])-getx(que[M]) ))L=M+1;
            else R=M;
        }
    	int j=que[L];
    	dis[i]=min(dis[i],value[j] + Int(i-j)*(i-j));
	}
	/*
	ans-i*i+2*i*j=value[j]+j*j
	*/
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	dijkstra(1);
	for(int i=1;i<=k;i++){
		Dynamic_programing();
		dijkstra(0);
	}
	for(int i=1;i<=n;i++)write(dis[i]),printf(" ");
	puts("");
	return 0;
}

输出：
0 1 2 5 8 

只改了getx的类型就挂了，为什么捏