题目传送门（内部题83）
输入格式
第一行两个整数$n,m$
接下来$m$行，每行三个整数，$u,v,w$，表示从$u$到$v$有一条权值为$w$的边
接下来一行有一个整数$q$，表示$q$天
接下来$q$行，每行三个整数，$s_i,t_i,k_i$，表示从$s_i$到$t_i$至少经过$k_i$条边
输出格式
一共$q$行，每行一个整数，表示在第$i$天中的最短距离，如果没有符合要求的答案，输出$-1$。
样例
样例输入：
3 3
1 2 1
2 3 10
3 1 100
3
1 1 1
1 2 1
1 3 1
样例输出：
111
1
11
数据范围与提示
对于$30\%$的数据，$k_ileqslant 50$
对于另外$30\%$的数据，$qleqslant 50$
对于$100\%$的数据，$nleqslant 50,mleqslant 10,000,wileqslant 10,000,qleqslant 100,000,kileqslant 10,000$
题解
$DP$和分块可能很难接合在一起，但是他们做到了。
不妨设$f[i][j][k]$表示从$i$到$j$恰好走$k$步的方案数，稍做修改就能做到至少走$k$步的方案数。
再设$p[i][j]$表示从$i$到$j$恰好走$100$步的方案数，这个数组也就是这道题的关键，将其分块了。
最后设$g[i][j][k]$表示从$i$到$j$恰好走$100 imes k$的方案数即可。
最后答案就是$minlimits_{i=1}^n(g[s][i][k/100]+f[i][t][k\%100])$。
时间复杂度：$Theta(100 imes n+q imes n)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int d[51][51],p[51][51],g[51][51][200],f[51][51][200];
int main()
{
memset(d,0x3f,sizeof(d));
memset(g,0x3f,sizeof(g));
memset(f,0x3f,sizeof(f));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
d[u][v]=min(d[u][v],w);
}
for(int i=1;i<=n;i++)
{
f[i][i][0]=0;
for(int j=0;j<n+100;j++)
for(int k=1;k<=n;k++)
for(int l=1;l<=n;l++)
f[i][l][j+1]=min(f[i][l][j+1],f[i][k][j]+d[k][l]);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
p[i][j]=f[i][j][100];
for(int k=n+100;~k;k--)
f[i][j][k]=min(f[i][j][k],f[i][j][k+1]);
}
for(int i=1;i<=n;i++)
{
g[i][i][0]=0;
for(int j=0;j<100;j++)
for(int k=1;k<=n;k++)
for(int l=1;l<=n;l++)
g[i][l][j+1]=min(g[i][l][j+1],g[i][k][j]+p[k][l]);
}
scanf("%d",&q);
while(q--)
{
int s,t,k,ans=0x3f3f3f3f;
scanf("%d%d%d",&s,&t,&k);
for(int i=1;i<=n;i++)ans=min(ans,f[i][t][k%100]+g[s][i][k/100]);
if(ans==0x3f3f3f3f)puts("-1");
else printf("%d
",ans);
}
return 0;
}
rp++