题意：给出一个有\(n\)个结点的有向图，边有边权。有\(q\)组询问，每次给出\(s,t,k\)，问从\(s\)到\(t\)至少经过\(k\)条边的最短路。
\(n \leq 50, \, q \leq 10^5, \, k \leq 10^4\)
首先，注意到\(n\)非常小这个性质。对于很多这类点数少，询问不易维护也不复杂的图论题，可以用矩阵来做。
我们设原图的邻接矩阵为\(G\)，并定义矩阵的二元运算\(\bigotimes\)为：
\[ (A \bigotimes B)_{ij} = \min_{k} A_{ik} + B_{kj} \] 那么，令\(A^k = \underbrace{A \bigotimes A \cdots A}_{k\text{ times}}\)，那么\((G^k)_{ij}\)就等于从\(i\)到\(j\)恰好走\(k\)步的最短路。因此，每次询问的答案就是\(G^k \bigotimes S\)，其中\(S\)为图floyd后得到的邻接矩阵。接下来，让我们考虑这样一个暴力：一开始对于所有可能的路径长度\(l \space (l \leq k + n )\)，求出\(G^l \bigotimes S\)。这样预处理是\(O(n^3 k)\)，询问是\(O(1)\)。
这样做的话，预处理复杂过高，但每次询问能允许更高的复杂度（\(O(n)\)）。注意到，询问要求的只是一个矩阵上的一个元素的罢了。因此，如果我们能把所有\(G^k \bigotimes S\)都表示为\(A \bigotimes B\)的形式，并且所有可能的\(A\)和\(B\)的总数量可以接受，就可以了。这也相当于把所有\(k\)拆分为两个数。
答案是分块。令块大小为\(H(k)\)，那么我们可以把\(k\)分为\(\left\lfloor \frac {k} {H(k)} \right\rfloor \times H(k) + k \mod H(k)\)的形式。因此，我们令\(H(k) = \sqrt k\)，那么，只要求出所有\(A_i = G^{i\sqrt k}, \ B_i = G_i \bigotimes S\)，就可以\(O(n)\)回答每次询问，且\(|A| = |B| = \sqrt k\)，故预处理复杂度也能达到\(O(n^3 \sqrt k)\)。
时间复杂度\(O(n^3 \sqrt k + nq)\)。
#includeusing namespace std;const int N = 55, BAS = 100, INF = 0x3f3f3f3f;typedef int mat[N][N];int n,m,q;mat a[N * 3],b[N * 3];void mul(mat& x,mat y,mat z) { memset(x,0x3f,sizeof(mat)); for (int k = 1 ; k <= n ; ++ k) for (int i = 1 ; i <= n ; ++ i) for (int j = 1 ; j <= n ; ++ j) x[i][j] = min(x[i][j],y[i][k] + z[k][j]);}int main() { int T,x,y,z,ret; scanf("%d",&T); while (T --) { scanf("%d%d",&n,&m); memset(a,0x3f,sizeof a); memset(b,0x3f,sizeof b); for (int i = 1 ; i <= m ; ++ i) { scanf("%d%d%d",&x,&y,&z); b[1][x][y] = min(b[1][x][y],z); } for (int i = 1 ; i <= n ; ++ i) a[0][i][i] = 0, b[0][i][i] = 0; for (int i = 2 ; i <= BAS + n ; ++ i) mul(b[i],b[i-1],b[1]); for (int i = 1 ; i <= n ; ++ i) for (int j = 1 ; j <= n ; ++ j) a[1][i][j] = b[100][i][j]; for (int i = 2 ; i <= BAS ; ++ i) mul(a[i],a[i-1],a[1]); for (int k = BAS + n - 1 ; k >= 0 ; -- k) for (int i = 1 ; i <= n ; ++ i) for (int j = 1 ; j <= n ; ++ j) b[k][i][j] = min(b[k][i][j],b[k+1][i][j]); scanf("%d",&q); for (int i = 1 ; i <= q ; ++ i) { scanf("%d%d%d",&x,&y,&z); ret = INF; for (int k = 1 ; k <= n ; ++ k) ret = min(ret,a[z/BAS][x][k] + b[z%BAS][k][y]); if (ret != INF) printf("%d\n",ret); else puts("-1"); } } return 0;}
小结：感觉分块白学了……还是只会死板地使用。