Chef and moon
All submissions for this problem are available.
Chef just went to moon , that too without any spacesuit ( chef is really talented ) , but when he reached moon , he discovered aliens living there . Now chef is at a city 'U' on moon and wants to travel to city 'V' , but the cars which aliens use can travel only K units distance in a day.
In this problem you are given the layout of moon and K . Chef will travel from U to V only if the shortest path from U to V is atmost K units . Given a few queries of U and V , answer whether chef can travel from U to V in a day or not .
The first line contains 3 integers integer N and M and K denoting the number of cities , number of roads and The distance the car can travel in a day. The next m lines contain 3 integers A ,B , C denoting there is a bidirectional road from A to B of distance C. The Next line contains the number of queries Q . Then Q lines follow each containing 2 integers U and V .
For each query , if the shortest path from U to V is less than or equal to K then output "YES" , otherwise "NO" in a separate line . If its not possible to visit city V from U , then also print "NO" only .
Input: 4 4 2 1 2 1 1 3 4 2 3 1 3 4 1 3 1 2 1 3 1 4 Output: YES YES NO
For 1st query , distance from 1 to 2 is 1 which is less then 2 so the answer is YES , for query 2 , shortest distance from 1 to 3 is 2 because chef can go from 1 to 2 (distance 1 ) and then from 2 to 3 (distance 1) , so total distance from 1 to 3 is 2 so the answer is YES . For 3rd query , the distance from 1 to 4 can not be less than 3 . so the answer is NO.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6|
Fetching successful submissions