## VMSS '15 #4 - Frank and Roads

View as PDF

Points: 10
Time limit: 2.5s
Memory limit: 256M

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

One of the reasons why Jeffrey is so scared of roads is that Frank is able to drive on them. Frank is not a very talented driver; in fact, he is one of the worst. However, Frank believes that he won't cause any accidents if the distance he drives is under kilometres.

Today, Frank needs to buy some apples. From his house, he plans to drive his car on the roads that Jeffrey is scared of in order to get to a Food Basics. To ensure that Frank doesn't cause any accidents, Frank will only visit a Food Basics that is under kilometres from his house. Help Frank find all of the Food Basics that he can visit.

#### Input Specification

The first line of input will contain four integers, , the number of kilometres that Frank can drive without seriously injuring someone, , the number of buildings that Frank can visit, , the number of roads that Frank can drive on, and , the number of Food Basics near Frank's house.

The next lines will contain an integer , denoting the buildings that are a Food Basics. Frank's house will never be a Food Basics. Who would want to live in a grocery store?

We define a road as a connection from one building to another. Each building is marked with a number from to . Frank's house will be denoted by the integer . The next lines will be in the form A B L, denoting a road that travels from building to building of length kilometres. The road can only be traveled in one direction.

#### Output Specification

Output the number of Food Basics that Frank can visit, within kilometres from his house.

#### Sample Input

15 3 5 2
2
3
0 1 2
1 2 10
1 3 20
0 3 22
0 2 15

#### Sample Output

1

#### Explanation

Shortest distance from Frank's house to building 2 is 12. Shortest distance from Frank's house to building 3 is 22. The only Food Basics reachable from Frank's house is building 2.

## Comments

• commented on June 15, 2019, 8:17 a.m.

I'm pretty sure that existing solutions have been subject to fairly weak test data. The following case whose answer is 1 will fail solutions that count stores kilometers away from Frank's house:

2 3 2 2
1
2
0 1 1
1 2 1

An incorrect solution in this respect will output 2. I have seen a couple of solutions which have received AC so far that do this.

As such, would it be possible to include the above case in the test data?

• commented on Sept. 28, 2020, 4:59 p.m.

i think this is a pretty misleading comment. a path to a food basics that is exactly T kilometres away is considered a valid path, so the correct output for ur test case is indeed 2 and not 1.

to be fair the question itself is very unclear, stating that a path has to be "under T kilometres", twice. thankfully the editorial is correct in saying that it is actually just supposed to be "no more than T km"

i am saying this because i originally had "<t" and had 6 test cases WA, but then changed it to "<=t" and got all AC

please correct me if im wrong

• commented on Sept. 23, 2018, 1:49 p.m.

I don't understand why my dijkstra's isn't working. It worked with a previous problem, so I don't understand why it isn't working now. Could someone check my code, please?

• commented on Sept. 23, 2018, 5:03 p.m.

The road can only be travelled in one direction.

• commented on Sept. 3, 2017, 9:15 p.m. edited

nvm

• commented on Aug. 3, 2017, 1:29 p.m. edited

Optimize my BFS?

How can I make my BFS faster? I'm TLE'ing the larger test cases and I'm pretty sure it's because my BFS repeats certain roads due to certain paths being faster than others yet being checked after the slower ones. Is there a way to speed things up?

EDIT: Nvm I AC'd after a few more changes.

• commented on Nov. 14, 2015, 9:47 p.m. edit 2

Two times, is stated to be the exclusive limit. It is inclusive.

What are the bounds on

Also can someone please explain to me how memset works.

• commented on Sept. 17, 2015, 9:53 p.m.

contrary to the problem statement

is not necessarily ≤

• commented on Sept. 18, 2015, 12:42 p.m. edit 2

Test data is fixed (probably). Comment again if you find any issues. All submissions are rejudged.

• commented on Sept. 17, 2015, 4:53 p.m.

Is it guaranteed to be no more than one road between each pair of buildings?

• commented on Sept. 17, 2015, 5:16 p.m.

Don't assume anything not explicitly mentioned.

• commented on Sept. 17, 2015, 4:22 p.m.

The problem says L <= T but you have L = 20 and 22 while T = 15

• commented on Sept. 17, 2015, 4:42 p.m.

Fixed.