题目解析
由于每个操作需要的权重都是一样的,所以本质上就是求 多源无权有向图最短路\bf{多源无权有向图最短路}多源无权有向图最短路,对于本题而言就是求从 i(1≤i≤n)i (1 \le i \le n)i(1≤i≤n) 移出 [1,n][1, n][1,n] 的最少步数。
令 dist[i] 表示从 iii 移出 [1,n][1, n][1,n] 的最小步数。
我们可以使用记忆化深度优先搜索来得到 dist[i]dist[i]dist[i]。
对于每个 [l,r][l, r][l,r] 的询问,遍历求出 max(dist[i])max(dist[i])max(dist[i]) 和 min(dist[i])(l≤i≤r,dist[i]≠∞)min(dist[i])(l \le i \le r, dist[i] \ne \infty)min(dist[i])(l≤i≤r,dist[i]=∞) 即可。
AC代码
复杂度分析
记忆化深搜求出 dist[i]dist[i]dist[i] 的时间复杂度为 O(n)O(n)O(n);
对于每个查询统计答案时间复杂度为 O(n)O(n)O(n);
总的时间复杂度为 O(nm)O(nm)O(nm)。