用李超线段树维护的式子，一直 RE。

是写法错了，还是空间小了？

提交记录

代码：

#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define PLI pair<long long,int>
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
#define debug cout<<"FUCK!!"<<endl;
int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*f;
}
const int N=2010,M=5010,mod=998244353;
const ll INF=2e18,LLMX=9e18;
int T,n,m,k,head[N],tot,vis[N][N<<2];ll dist[N][N<<2],distl[N][N<<2],fl[N],fr[N];
struct node{int to,nxt,w;}edge[M<<1];
void add(int x,int y,int w){edge[++tot]={y,head[x],w},head[x]=tot;}
void init(){
	FOR(i,0,n) FOR(j,0,4*n+10) dist[i][j]=distl[i][j]=INF;
	dist[1][0]=distl[n][0]=0;
	FOR(step,1,4*n+1) FOR(x,1,n){
		for(int i=head[x];i;i=edge[i].nxt){
			int y=edge[i].to;
			dist[y][step]=min(dist[y][step],dist[x][step-1]+edge[i].w);
			distl[y][step]=min(distl[y][step],distl[x][step-1]+edge[i].w);
		}
	}
}
void solve(){
	ll ans=0;
	FOR(i,0,k) if(dist[n][i]!=INF) ans=(ans+dist[n][i])%mod;
	printf("%lld\n",ans);
}
int qpow(int a,int b){
	int res=1;
	while(b){if(b&1)res=1ll*res*a%mod;a=1ll*a*a%mod,b>>=1;}
	return res;
}

//segment tree
int cnt,rt,idx,seg[M*50],ls[M*50],rs[M*50];
struct Node{ll k,b;}p[N];
ll calc(int id,int x){
	return p[id].k*x+p[id].b;
}
void update(int &u,int l,int r,int id){
	if(!u) u=++idx;
	int mid=(l+r)>>1,&g=seg[u];
	if(calc(id,mid)<calc(g,mid)) swap(g,id);
	if(calc(id,l)<calc(g,l)) update(ls[u],l,mid,id);
	if(calc(id,r)<calc(g,r)) update(rs[u],mid+1,r,id);
}
void modify(int &u,int l,int r,int ql,int qr,int id){
	if(!u) u=++idx;
	if(ql<=l&&r<=qr){update(u,l,r,id);return;}
	int mid=(l+r)>>1;
	if(ql<=mid) modify(ls[u],l,mid,ql,qr,id);
	if(qr>mid) modify(rs[u],mid+1,r,ql,qr,id);
}
PLI pmn(PLI a,PLI b){
	if(a.fi<b.fi) return a;
	return b;
}
PLI query(int u,int l,int r,int v){
	if(l>v||r<v) return mp(LLMX,0);
	int mid=(l+r)>>1;PLI res=mp(calc(seg[u],v),seg[u]);
	if(l==r) return res;
	return pmn(res,pmn(query(ls[u],l,mid,v),query(rs[u],mid+1,r,v)));
}

int main(){
	T=rd;int inv2=qpow(2,mod-2);
	while(T--){
		memset(head,0,sizeof(head)),tot=0;
		n=rd,m=rd,k=rd;
		FOR(i,1,m){int x=rd,y=rd,w=rd;add(x,y,w),add(y,x,w);}
		init();
		if(k<=4*n){solve();continue;}
		FOR(i,0,n) fl[i]=fr[i]=INF;
		FOR(i,1,n) FOR(j,0,4*n) fl[i]=min(fl[i],dist[i][j]+distl[i][4*n-j]);
		FOR(i,1,n) FOR(j,0,4*n+1) fr[i]=min(fr[i],dist[i][j]+distl[i][4*n+1-j]);
		ll ans=0;
		FOR(i,0,4*n) if(dist[n][i]<INF) ans=(ans+dist[n][i])%mod;
		p[0].k=1e9,p[0].b=INF*3ll;
		cnt=rt=idx=0,memset(seg,0,sizeof(seg)),memset(ls,0,sizeof(ls)),memset(rs,0,sizeof(rs));
		FOR(x,1,n) for(int i=head[x];i;i=edge[i].nxt){
			int w=edge[i].w;
			if(fr[x]<INF) p[++cnt]={w,fr[x]-(4ll*n+1)*w},modify(rt,1,1e9,1,1e9,cnt);
		}
		if(cnt){
			auto cal=[&](int k){
				k=k*2+1;
				return query(rt,1,1e9,k).fi;
			};
			int t=n*2,lim=(k-1)>>1;
			while(t<=lim){
				ll tmp=cal(t);
				if(t==lim){ans=(ans+tmp)%mod;break;}
				int l=t+1,r=lim;ll d=cal(t+1)-tmp;
				while(l<r){
					int mid=(l+r+2)>>1;
					if(cal(mid)==tmp+d*(mid-t)) l=mid;
					else r=mid-1;
				}
				ans=(ans+tmp%mod*(l-t+1)%mod)%mod;
				ans=(ans+1ll*(l-t+1)*(l-t)%mod*inv2%mod*d%mod)%mod;
				t=l+1;
			}
		}
		p[0].k=1e9,p[0].b=INF*4ll;
		cnt=rt=idx=0,memset(seg,0,sizeof(seg)),memset(ls,0,sizeof(ls)),memset(rs,0,sizeof(rs));
		FOR(x,1,n) for(int i=head[x];i;i=edge[i].nxt){
			int w=edge[i].w;
			if(fl[x]<INF) p[++cnt]={w,fl[x]-4ll*n*w},modify(rt,1,1e9,1,1e9,cnt);
		}
		if(cnt){
			auto cal=[&](int k){
				k=k*2;
				return query(rt,1,1e9,k).fi;
			};
			int t=n*2+1,lim=(k>>1);
			while(t<=lim){
				ll tmp=cal(t);
				if(t==lim){ans=(1ll*ans+tmp)%mod;break;}
				int l=t+1,r=lim;ll d=cal(t+1)-tmp;
				while(l<r){
					int mid=(l+r+2)>>1;
					if(cal(mid)==tmp+d*(mid-t)) l=mid;
					else r=mid-1;
				}
				ans=(ans+tmp%mod*(l-t+1)%mod)%mod;
				ans=(ans+1ll*(l-t+1)*(l-t)%mod*inv2%mod*d%mod)%mod;
				t=l+1;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}