2023-10-07
题目
题目描述
Travelling Through the Snow Queen's Kingdom
输入样例
5 4 6
1 2
2 3
3 4
3 5
1 3 1 4
1 3 2 4
1 4 4 5
1 4 4 1
2 3 1 4
2 2 2 3
输出样例
Yes
Yes
Yes
No
No
Yes
难度&重要性(1~10):7.5
题目来源
CQYC
题目算法
dp
解题思路
这道题有一个很有意思的地方，就是我们经过第 \(i\) 条边一定是在第 \(i\) 个时刻的，这样我们就不难发现这个路径是单调上升的。所以走一条边花费 \(1\) 根本没有用。
那么其实我们每一次处理询问的时候对于 \(<l_i\) 的边我们是可以直接不用计算的，就相当于是把 \(<l_i\) 的边删掉一样。这样我们考虑换一个角度，我们从编号大的边开始想图中加边，同时我们用新加的这条边对于先前有的边进行一个更新就行 Floyd 一样。这样也可以达到相同的效果。
这样我们只需要把 \(q\) 次询问离线下来，当加到第 \(l_i\) 时再更新答案即可。
完成状态
已完成