ddp 简单题。

原图是个 DAG。而且可以按照编号除以 $k$ 的值来分层，每一层节点的个数都很少，这启示我们设计 dp。

设 $f_{i,u}$ 表示从起点到达第 $i$ 层节点 $u$ 的最短路径，设从 $i-1$ 层的节点 $v$ 到达第 $i$ 层的节点 $u$ 的距离为 $w_{i-1,u,v}$，没有则为 $-\infty$。则有：

$$f_{i,u}=\min_{v=1}^k\{f_{i-1,v}+w_{u,v}\}$$

用矩阵刻画 dp 转移，设

$$F_i=\left[\begin{matrix}f_{i,1}&f_{i,2}&\dots&f_{i,k}\end{matrix}\right]$$$$A_{i}=\left[\begin{matrix}w_{i,1,1}&w_{i,1,2}&\dots &w_{i,1,k}\\w_{i,2,1}&w_{i,2,2}&\dots& w_{i,2,k}\\ \vdots&\vdots&\ddots&\vdots\\w_{i,k,1}&w_{i,k,2}&\dots &w_{i,k,k}\end{matrix}\right]$$

则利用广义矩阵乘法，将 $\min+$ 两种运算组合，则有

$$F_i\times A_i=F_{i+1}$$

用线段树维护矩阵 $A$ 的乘积和即可。

时间复杂度 $O(n\log nk^3)$。

#include <iostream>
#include <cstdio>
#include <cstring> 
using namespace std;
const int N=5e4+10,inf=1e9+7;
int k,n,m,q,p;
struct mat{
	int n,m,x[5][5];
	void init(int r,int c){n=r,m=c;memset(x,0x3f,sizeof(x));}
}G[N],val[N<<2],tmp;
mat operator * (const mat &a,const mat &b){
	mat c;c.init(a.n,b.m);
	for(int i=0;i<a.n;i++)
		for(int j=0;j<a.m;j++)
			for(int k=0;k<b.m;k++)
				c.x[i][j]=min(c.x[i][j],a.x[i][k]+b.x[k][j]);
	return c;
}
struct sgt{
	#define ls p<<1
	#define rs p<<1|1
	void build(int p,int l,int r){
		val[p]=G[l];if(l==r)return;
		int mid=(l+r)>>1;
		build(ls,l,mid),build(rs,mid+1,r);
		val[p]=val[ls]*val[rs];
	}
	void ask(int p,int l,int r,int L,int R){
		if(L<=l&&r<=R){tmp=tmp*val[p];return;}
		int mid=(l+r)>>1;
		if(L<=mid)ask(ls,l,mid,L,R);
		if(R>mid)ask(rs,mid+1,r,L,R);
	}
}tr;
int main(){
	scanf("%d %d %d %d",&k,&n,&m,&q);p=(n-1)/k;
	for(int i=1;i<=p;i++)G[i].init(5,5);
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d %d %d",&u,&v,&w);
		G[v/k].x[u%k][v%k]=w;
	}
	tr.build(1,1,p);
	while(q--){
		int a,b,ans=inf;
		scanf("%d %d",&a,&b);
		tmp.init(1,5),tmp.x[0][a%k]=0;//初始化
		if(a/k+1<=b/k)tr.ask(1,1,p,a/k+1,b/k);
		if(tmp.x[0][b%k]<inf)printf("%d\n",tmp.x[0][b%k]);//注意特判
		else printf("-1\n");
	}
	return 0;
}

如有错误，请指出。