VMSS '15 #4 - Frank and Roads

View as PDF
Submit solution
Points: 10
Time limit: 2.5s
Memory limit: 256M
Authors:
JeffreyZ, LeoF
Problem type

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 T 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 T 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, T (1 \le T \le 10^5), the number of kilometres that Frank can drive without seriously injuring someone, N (1 \le N \le 2\,000), the number of buildings that Frank can visit, M (1 \le M \le 86\,000), the number of roads that Frank can drive on, and G (1 \le G \le N), the number of Food Basics near Frank's house.

The next G lines will contain an integer g_i (1 \le g_i \le N), 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 1 to N. Frank's house will be denoted by the integer 0. The next M lines will be in the form A B L, denoting a road that travels from building A to building B of length L kilometres. The road can only be traveled in one direction.

Output Specification

Output the number of Food Basics that Frank can visit, within T 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


  • 0
    max  commented on June 15, 2019, 12:17 p.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 T 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?


    • 3
      cabbagecabbagecabbage  commented on Sept. 28, 2020, 8: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


  • 0
    Cameron  commented on Sept. 23, 2018, 5: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?


    • 0
      Relativity  commented on Sept. 23, 2018, 9:03 p.m.

      The road can only be travelled in one direction.


  • 3
    bobhob314  commented on Nov. 15, 2015, 2:47 a.m. ← edit 2

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

    What are the bounds on L?

    Also can someone please explain to me how memset works.


  • 0
    cheesecake  commented on Sept. 17, 2015, 8:53 p.m.

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


    • 1
      FatalEagle  commented on Sept. 17, 2015, 9:16 p.m.

      Don't assume anything not explicitly mentioned.