FASTFOOD - Fast Food Restaurant

no tags 

Hong Kil Dong wants to open a new fast food restaurant to make some money. The picture below describes the city where he wants to open his restaurant. The nodes are the possible locations that he can set up his new restuarant, and the edges are the length of the road connecting the two locations. You can assume that maximum five roads intersect at a single node, and that it is possible to reach all nodes from any chosen node.

There are three apartments (these three are the only places people live in) in this city, denoted A, B, and C, as shown in the picture.


Suppose he wants to open his new restuarant in location (node) 1. The shortest distances from location 1 to A, B, and C are 8, 16, and 9 respectively. These values are each larger than the shortest distances from location 4 to A, B, and C, which are 6, 7, and 3. Since people usually prefer using closer restuarants, it is better to open his restaurant in location 4.

Consider location 6. The shortest distances from location 6 to A, B, and C are 5, 3, and 5. Therefore, location 6 is better than location 1. However, when comparing with location 4, it is better regarding A and B, but worse when considering C.

Therefore, Hong Kil Dong came up with a criteria to determine whether a given location is good or bad.

Consider location p, and let the shortest distances from location p to A, B, and C be a, b, and c, respectively.        

Consider another location q, and let the shortest distances from location q to A, B, and C be x, y, z, respectively.

If a>x, b>y and c>z, we say that location p is a bad location. If there is no location q that satisfies this, we say that location p is a good location.

Hong Kil Dong has chosen some candidate locations. Given the description of the city and a number of queries, determine whether each candidate location is good or bad.

Note that it is possible to open the restaurant in any of the locations, even in  A, B, and C.


The first line of the input is an integer N (1<=N<=100,000), denoting the number of locations.  All the locations are numbered from 1-N.

The second line of the input is three integers A, B, and C, denoting the location of each apartment. A, B, and C are all distinct and are between 1 and N, inclusive.

The third line of the input is M, denoting the number of roads in this city.

The next M lines give the description of each road and consist of integer X, Y, and Z (1<=Z<=10,000). X and Y are the two endpoints of this road, and Z is the length of this road. No two same roads appear in the input.

The next line is an integer T (1<=T<=10,000), denoting the number of queries.

The next T lines each consist of an integer Q (1<=Q<=N), which denote the location number. 


For each query, determine whether location Q is a good location or a bad location. If it is bad, output "NO" (quotes for clarity) and "YES" if it is good.


2 5 9
1 2 8
1 3 5
2 4 6
2 5 8
2 6 5
3 4 6
3 9 4
4 6 4
4 9 3
5 6 3
5 7 4
6 7 2
6 9 5
7 8 7
8 9 6
Output: NO

hide comments
lnuic: 2015-12-30 12:31:30


=(Francky)=> Quickly restored with your link. Many thanks.

Last edit: 2015-12-30 19:56:38
stranger: 2013-07-06 15:11:19

plz update the picture

sevenkplus: 2011-02-13 14:05:58

The distance from location 1 to apartment C should be 9, not 19.

Problem Uploader: sorry for the typo. Fixed.

Last edit: 2011-02-13 14:06:40
Dominik Kempa: 2011-02-13 14:05:58

NICEDAY is a little easier due to non-conflicting values on each axis.

[Rampage] Blue.Mary: 2011-02-13 14:05:58

See problem NICEDAY.

Siarhei Kulik: 2011-02-13 14:05:58

When will we able to submit solutions for this problem?

Hy Trường Sơn: 2011-02-13 14:05:58

nice problem!

Added by:Lawl
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:2010 KOI Final Stage Middle School & High School Division