A10388. Travelling Through the Snow Queen's Kingdom
编程题
普及/提高-
知识点
题目描述
Gerda is travelling to the palace of the Snow Queen.
The road network consists of $n$ intersections and $m$ bidirectional roads. Roads are numbered from $1$ to $m$ . Snow Queen put a powerful spell on the roads to change the weather conditions there. Now, if Gerda steps on the road $i$ at the moment of time less or equal to $i$ , she will leave the road exactly at the moment $i$ . In case she steps on the road $i$ at the moment of time greater than $i$ , she stays there forever.
Gerda starts at the moment of time $l$ at the intersection number $s$ and goes to the palace of the Snow Queen, located at the intersection number $t$ . Moreover, she has to be there at the moment $r$ (or earlier), before the arrival of the Queen.
Given the description of the road network, determine for $q$ queries $l_{i}$ , $r_{i}$ , $s_{i}$ and $t_{i}$ if it's possible for Gerda to get to the palace on time.
The road network consists of $n$ intersections and $m$ bidirectional roads. Roads are numbered from $1$ to $m$ . Snow Queen put a powerful spell on the roads to change the weather conditions there. Now, if Gerda steps on the road $i$ at the moment of time less or equal to $i$ , she will leave the road exactly at the moment $i$ . In case she steps on the road $i$ at the moment of time greater than $i$ , she stays there forever.
Gerda starts at the moment of time $l$ at the intersection number $s$ and goes to the palace of the Snow Queen, located at the intersection number $t$ . Moreover, she has to be there at the moment $r$ (or earlier), before the arrival of the Queen.
Given the description of the road network, determine for $q$ queries $l_{i}$ , $r_{i}$ , $s_{i}$ and $t_{i}$ if it's possible for Gerda to get to the palace on time.
输入格式
The first line of the input contains integers $n$ , $m$ and $q$ ( $2<=n<=1000$ , $1<=m,q<=200000$ ) — the number of intersections in the road network of Snow Queen's Kingdom, the number of roads and the number of queries you have to answer.
The $i$ -th of the following $m$ lines contains the description of the road number $i$ . The description consists of two integers $v_{i}$ and $u_{i}$ ( $1<=v_{i},u_{i}<=n$ , $v_{i}≠u_{i}$ ) — the indices of the intersections connected by the $i$ -th road. It's possible to get both from $v_{i}$ to $u_{i}$ and from $u_{i}$ to $v_{i}$ using only this road. Each pair of intersection may appear several times, meaning there are several roads connecting this pair.
Last $q$ lines contain the queries descriptions. Each of them consists of four integers $l_{i}$ , $r_{i}$ , $s_{i}$ and $t_{i}$ ( $1<=l_{i}<=r_{i}<=m$ , $1<=s_{i},t_{i}<=n$ , $s_{i}≠t_{i}$ ) — the moment of time Gerda starts her journey, the last moment of time she is allowed to arrive to the palace, the index of the starting intersection and the index of the intersection where palace is located.
The $i$ -th of the following $m$ lines contains the description of the road number $i$ . The description consists of two integers $v_{i}$ and $u_{i}$ ( $1<=v_{i},u_{i}<=n$ , $v_{i}≠u_{i}$ ) — the indices of the intersections connected by the $i$ -th road. It's possible to get both from $v_{i}$ to $u_{i}$ and from $u_{i}$ to $v_{i}$ using only this road. Each pair of intersection may appear several times, meaning there are several roads connecting this pair.
Last $q$ lines contain the queries descriptions. Each of them consists of four integers $l_{i}$ , $r_{i}$ , $s_{i}$ and $t_{i}$ ( $1<=l_{i}<=r_{i}<=m$ , $1<=s_{i},t_{i}<=n$ , $s_{i}≠t_{i}$ ) — the moment of time Gerda starts her journey, the last moment of time she is allowed to arrive to the palace, the index of the starting intersection and the index of the intersection where palace is located.
输出格式
For each query print "Yes" (without quotes) if Gerda can be at the Snow Queen palace on time (not later than $r_{i}$ ) or "No" (without quotes) otherwise.
输入输出样例
输入 #1
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
输出 #1
Yes Yes Yes No No Yes