传送门

基于Floyd的动态规划原理，我们可以只用进行一次Floyd。

而题目给出的限制条件相当于给Floyd加了时间限制而已。

还是得靠对Floyd的理解。

——代码

1 #include <cstdio> 2 #include <iostream> 3 4 using namespace std; 5 6 const int MAXN = 201, INF = 23333333; 7 int n, m, q; 8 int t[MAXN], dis[MAXN][MAXN], qx[50001], qy[50001], qt[50001]; 9 10 int main() 11 24 scanf("%d", &q); 25 for(i = 1; i <= q; i++) scanf("%d %d %d", &qx[i], &qy[i], &qt[i]); 26 for(l = 1; l <= q; l++) 27 35 if(t[qx[l]] > qt[l] || t[qy[l]] > qt[l] || dis[qx[l]][qy[l]] == INF) printf("1\n"); 36 else printf("%d\n", dis[qx[l]][qy[l]]); 37 } 38 return 0; 39 }
View Code