传送门
基于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
上一篇：[HDU4417]Super Mario（主席树+离散化）
下一篇：[luoguP2420] 让我们异或吧（dfs + 异或的性质）
最短路 Floyd
