算是回归OI后第一道自己写的题（考CSP的时候可没回归）
写篇题解纪念一下
题目大意： \(n\) 个点，\(m\) 条单向边，每条边的两端点 \(x\),\(y\)必定满足 \(\left\lfloor\dfrac{y}{k}\right\rfloor=\left\lfloor\dfrac{x}{k}\right\rfloor+1\), \(q\)次询问，求每一对\(a\),\(b\)的最短距离。
\(n<=5*10^{4},q<=10^4\)\(1<k<5\),保证\(a\)<\(b\)
简单分析一下容易发现这是个分层图，每 \(k\) 个点为一层，只有相邻的层间有边且边只能往编号大的方向去。
然后就是考虑这个东西怎么维护了，考虑前两天CSP2022的T4做法之一，矩阵乘法+倍增优化dp
容易发现我们可以把每个层缩成一个点，之后的图就成了好多条链（注意不一定保证联通）
然后对于这条链中的每两个相邻节点（即相邻两层），我们可以用类似Floyd的方法把原图中的边构造一个矩阵，接着就可以矩阵乘法快速合并了。
然后再倍增处理一下就结束了
记得判连通性。
（我自己的实现把链当成树了所以看起来有些麻烦。。。但是问题不大，能过就行）
点击查看代码
#include <bits/stdc++.h>
#define N 50010
#define M 1000010
#define pii pair<int,int>
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
//#define int long long
//#define MOD
#define INF 1000000000
#define int_edge int to[M],nxt[M],head[N],cnt=0;
using namespace std;
int k,n,m,q,fa[N][16],f[N],dep[N],eid=0,vis[N];
int_edge;void add_edge(int x,int y ){to[++cnt]=y;nxt[cnt]=head[x];head[x]=cnt;}
map<pii,int>mp;
struct Y{int x,y,t;};vector<Y>E[N];
int id(int x){return x/k+1;}
//int_edge;int val[M];void add_edge(int x,int y,int z){to[++cnt]=y;val[cnt]=z;nxt[cnt]=head[x];head[x]=cnt;}
struct Matrix{
int a[5][5];
Matrix(){memset(a,0x3f,sizeof(a));}
Matrix operator * (const Matrix &y){
Matrix sum;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
for(int k=0;k<5;k++)
sum.a[i][j]=min(sum.a[i][j],a[i][k]+y.a[k][j]);
return sum;
}
}dn[N][16];
Matrix init(){
Matrix x;for(int i=0;i<k;i++)x.a[i][i]=0;return x;
}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void dfs(int nw,int lst){
vis[nw]=1;
fa[nw][0]=lst;dep[nw]=dep[lst]+1;
if(lst!=0){
for(auto e:E[mp[mkp(lst,nw)]]){
dn[nw][0].a[e.x%k][e.y%k]=e.t;
}
}
for(int i=1;i<=15;i++){
fa[nw][i]=fa[fa[nw][i-1]][i-1];
dn[nw][i]=dn[fa[nw][i-1]][i-1]*dn[nw][i-1];
}
for(int i=head[nw];i;i=nxt[i])
if(to[i]!=lst)dfs(to[i],nw);
}
signed main()
{
scanf("%d %d %d %d",&k,&n,&m,&q);
for(int i=0;i<n;i++)f[i]=i;
for(int i=1,x,y,t;i<=m;i++){
scanf("%d %d %d",&x,&y,&t);
f[find(x)]=find(y);
if(mp.find(mkp(id(x),id(y)))==mp.end()){
mp[mkp(id(x),id(y))]=++eid;
add_edge(id(x),id(y));
}
E[mp[mkp(id(x),id(y))]].pb(Y{x,y,t});
}
for(int i=1;i<=id(n);i++)if(!vis[i])dfs(i,0);
while(q--){
int x,y;scanf("%d %d",&x,&y);
if(find(x)!=find(y)){puts("-1");continue;}
int id1=id(x),id2=id(y);
Matrix ans=init();
for(int i=15;i>=0;i--)
if(dep[fa[id2][i]]>=dep[id1])
ans=dn[id2][i]*ans,id2=fa[id2][i];
if(ans.a[x%k][y%k]==1061109567)puts("-1");
else printf("%d\n",ans.a[x%k][y%k]);
}
return 0;
}