题意：

给出n个点，m条有向边，有q次询问，问从s到t至少经过$k_i$条路的最短路为多少。其中$1≤T≤10,2≤n≤50,1≤q≤100000,1≤k_i≤10000$。

思路：

dp也可以分块啊 感觉开拓了我的思路啊(๑•̀ㅂ•́)و✧真有趣！

这里有两份比较好的题解：

https://blog.csdn.net/weixin_42068627/article/details/81299321

https://blog.csdn.net/qq_34454069/article/details/81292814

首先考虑最朴素的dp，$dp[k][i][j]$：从i到j至少走k条路的最短路。有转移：$dp[k][i][j]=min(dp[k-1][i][l]+d[l][j])|1≤l≤n且l≠j$，其中$d[i][j]$表示i到j的最短路。

复杂度是$O(T*k*n^3)$，结合数据范围，这有$10^{10}$。当然不可能是这么做的啦。

那么考虑倍增？

$dp1[k][i][j]$：从i到j恰好走$2^k$条路的最短路。

$dp2[k][i][j]$：从i到j至少走$2^k$条路的最短路。

有转移：

$dp1[k][i][j]=min(dp1[k-1][i][l]+dp1[k-1][l][j])|1≤l≤n$。

$dp2[k][i][j]=min(dp1[k-1][i][l]+d[k-1][l][j])|1≤l≤n$。

预处理的复杂度是$O(T*log_2k*n^3)$，结合数据范围，这是$10^7$，对于每次询问，枚举中转点i，$ans[k][i][j]=dp2[k的二进制形式中的1][i][l]+dp1[k-k的二进制中的1][l][j]$，而这里的也需要二进制中的1也要循环处理，处理询问的复杂度为$O(q*T*n*log_2k)$，结合数据范围，这是$7*10^8$，似乎也不太行啊？

所以考虑分块。

假设分成M块，$M=\sqrt k$。

$dp[k][i][j]$：从i到j恰好走k条路的最短路$(k≤M)$。

$dp1[k][i][j]$：从i到j至少走k条路的最短路$(k≤M)$。

$dp2[k][i][j]$：从i到j恰好走M*k条路的最短路。

有转移：

$dp[k][i][j]=min(dp[k-1][i][l]+w[l][j])|1≤l≤n且l≠j$。

$dp1[k][i][j]=min(dp1[k-1][i][l]+d[l][j])|1≤l≤n且l≠j$。

$dp2[k][i][j]=min(dp2[k-1][i][l]+dp[M][l][j])|1≤l≤n$。

预处理的复杂度是$O(T*M*n^3)$，结合数据范围，这是$10^8$，对于每个询问，枚举中转点l，$ans[k][i][j]=min(dp2[k/m][i][l]+dp1[k\%m][l][j])$，复杂度为$O(T*q*n)$，相比倍增，这个复杂度是可以接受的。

代码：

int g[55][55];
int d[55][55];
int dp[110][55][55];//从i到j恰好走k条路的最短路
int dp1[110][55][55];//从i到j至少走k条路的最短路
int dp2[110][55][55];//从i到j恰好走k*100条路的最短路
int main()
{
    int t,n,m,x,y,z,q;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(g,INF,sizeof(g));
        for(int i=1;i<=n;i++)
            g[i][i]=0;
        while(m--)
        {
            scanf("%d%d%d",&x,&y,&z);
            g[x][y]=min(g[x][y],z);
        }
        /*for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                printf("%d ",g[i][j]);
            printf("\n");
        }
        printf("\n");*/
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]=g[i][j];
        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        /*for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
                printf("%d ",d[i][j]);
            printf("\n");
        }
        printf("\n");*/
        memset(dp,INF,sizeof(dp));
        for(int i=1;i<=n;i++)
            dp[0][i][i]=0;
        for(int k=1;k<=100;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    for(int l=1;l<=n;l++)
                       if(l!=j)dp[k][i][j]=min(dp[k][i][j],dp[k-1][i][l]+g[l][j]);
        /*for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            printf("dp[%d][%d][%d]=%d\n",k,i,j,dp[k][i][j]);
        printf("\n");*/
        memset(dp1,INF,sizeof(dp1));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
               dp1[0][i][j]=d[i][j];
        for(int k=1;k<=100;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    for(int l=1;l<=n;l++)
                        if(l!=j)dp1[k][i][j]=min(dp1[k][i][j],dp1[k-1][i][l]+d[l][j]);
        /*for(int k=0;k<=n;k++)
            for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            printf("dp[%d][%d][%d]=%d\n",k,i,j,dp1[k][i][j]);
        printf("\n");*/
        memset(dp2,INF,sizeof(dp2));
        for(int i=1;i<=n;i++)
            dp2[0][i][i]=0;
        for(int k=1;k<=100;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                    for(int l=1;l<=n;l++)
                        dp2[k][i][j]=min(dp2[k][i][j],dp2[k-1][i][l]+dp[100][l][j]);
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d%d",&x,&y,&z);
            int p1=z/100,p2=z%100;
            int ans=INF;
            for(int l=1;l<=n;l++)
                ans=min(ans,dp2[p1][x][l]+dp1[p2][l][y]);
            if(ans==INF)printf("-1\n");
            else printf("%d\n",ans);
        }
    }
    return 0;
}