分块floyd
$f[i][j][k]$表示从i走k步到j的最短路
$g[i][j][k]$表示从i走k*100步到j的最短路
$h[i][j][k]$表示从i至少走k步到j的最短路
询问从x到y至少走z步的最短路时，因为至多多走n步，用上面预处理的f,g,h可以得出答案。
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define Formylove return 0
13 #define For(i,a,b) for(int i=(a);i<=(b);i++)
14 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
15 const int N=55;
16 typedef long long LL;
17 typedef double db;
18 using namespace std;
19 int T,n,m,f[N][N][205],g[N][N][205],h[N][N][205];
20
21 template<typename T>void read(T &x) {
22 char ch=getchar(); x=0; T f=1;
23 while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
24 if(ch=='-') f=-1,ch=getchar();
25 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
26 }
27
28 //Walking Plan hdu6331
29 int main() {
30 #ifdef ANS
31 freopen(".in","r",stdin);
32 freopen(".out","w",stdout);
33 #endif
34 read(T);
35 while(T--) {
36 read(n); read(m);
37
38 memset(f,127/3,sizeof(f));
39 memset(g,127/3,sizeof(g));
40 memset(h,127/3,sizeof(h));
41
42 int inf=f[0][0][0];
43
44 For(i,1,n) f[i][i][0]=g[i][i][0]=h[i][i][0]=0;
45
46 For(i,1,m) {
47 int u,v,w;
48 read(u); read(v); read(w);
49 f[u][v][1]=min(f[u][v][1],w);
50 }
51
52 For(k,2,200) {
53 For(l,1,n) For(i,1,n) For(j,1,n)
54 f[i][j][k]=min(f[i][j][k],f[i][l][k-1]+f[l][j][1]);
55 }
56
57 For(i,1,n) For(j,1,n) g[i][j][1]=f[i][j][100];
58 For(k,2,100)
59 For(l,1,n) For(i,1,n) For(j,1,n)
60 g[i][j][k]=min(g[i][j][k],g[i][l][k-1]+g[l][j][1]);
61 For(i,1,n) For(j,1,n) For(k,1,100)
62 For(l,k,200) h[i][j][k]=min(h[i][j][k],f[i][j][l]);
63
64 int q;
65 read(q);
66 while(q--) {
67 int i,j,z;
68 read(i); read(j); read(z);
69 int ans=inf;
70 For(k,1,n) {
71 int a=z/100,b=z%100;
72 if(b==0) a--,b=100;
73 ans=min(ans,g[i][k][a]+h[k][j][b]);
74 }
75 if(ans>=inf) ans=-1;
76 printf("%d
",ans);
77 }
78 }
79 Formylove;
80 }
81 /*
82 Sample Input
83 2
84 3 3
85 1 2 1
86 2 3 10
87 3 1 100
88 3
89 1 1 1
90 1 2 1
91 1 3 1
92 2 1
93 1 2 1
94 1
95 2 1 1
96 Sample Output
97 111
98 1
99 11
100 -1
101 */