VMSS '15 #4 - Frank and Roads

View as PDF

Submit solution

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

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 \leq T \leq 10^5), the number of kilometres that Frank can drive without seriously injuring someone, N (1 \leq N \leq 2\,000), the number of buildings that Frank can visit, M (1 \leq M \leq 86\,000), the number of roads that Frank can drive on, and G (1 \leq G \leq 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
0 1 2
1 2 10
1 3 20
0 3 22
0 2 15

Sample Output



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.


  • 1
    max  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 T kilometers away from Frank's house:

    2 3 2 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, 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

  • 0
    Cameron  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?

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

      The road can only be travelled in one direction.

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


  • 0
    aeternalis1  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.

  • 4
    bobhob314  commented on Nov. 14, 2015, 9:47 p.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.

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

    contrary to the problem statement

    g\_{i} is not necessarily ≤ N

    • 1
      FatalEagle  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.

  • 0
    cheesecake  commented on Sept. 17, 2015, 4: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, 5:16 p.m.

      Don't assume anything not explicitly mentioned.

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

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

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