CCC '03 S5 - Trucking Troubles

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M
Problem type
Canadian Computing Competition: 2003 Stage 1, Senior #5

You are a salesperson selling trucks which can carry trucks which can carry trucks. Needless to say, your trucks are heavy. Also needless to say, you have to drive one of these trucks across a wide wet domain, and since it is wet, you need to drive over some bridges. In fact, on every road between two cities, there is a bridge but there is not a direct road between every pair of cities. Each bridge can support a certain maximum weight. This maximum weight is an integer from 0 to 100\,000.

You have been given a list of cities where there are customers who are eager to view one of your trucks. These cities are called destination cities. Since you must decide which truck you will drive through these cities, you will have to answer the following problem: what is the maximum weight that can be driven through these destination cities? You are to write a program to solve this problem.

The first line of input will contain three positive integers: c, r and d specifying the number of cities (in total), number of roads between cities and number of destination cities, respectively. The cities are numbered from 1 to c. There are at most 10\,000 cities and at most 100\,000 roads. The next r lines contain triples x\ y\ w indicating that this road runs between city x and city y and it has a maximum weight capacity of w. The next d lines give the destination cities you must visit with your truck. There will be at least one destination city.

You can assume that you are starting in city 1 and that city 1 is not a destination city. You can visit the d destination cities in any order, but you must visit all d destination cities.

The output from your program is a single integer, the largest weight that can be driven through all d destination cities.

Note that 15 of the available 16 marks are for the original test data used during the competition, and the remaining mark is dedicated to hacking improper solutions.

Sample Input

5 7 3
1 2 20
1 3 50
1 4 70
1 5 90
2 3 30
3 4 40
4 5 60
2
4
5

Output for Sample Input

30

Comments


  • 0
    wedoalittle_trolling  commented on Jan. 7, 2024, 10:59 p.m.

    What is the highest value d can be?


  • -8
    maxcruickshanks  commented on Feb. 20, 2023, 1:31 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -8
      maxcruickshanks  commented on Aug. 6, 2023, 3:36 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • 0
    Bolaloon  commented on Jan. 17, 2023, 2:00 p.m.

    I think this question needs the test case:

    3 3 1
1 2 20
1 3 20
3 2 30
2

    The correct output is 20, but most people have programs that output 30.


  • 2
    ht2012  commented on Jan. 5, 2018, 10:09 a.m.

    :( how do you allocate memory in c to do the matrix thing? I'm only getting RTE for the last point, probably cuz it bursts my stack every time.


    • 4
      wleung_bvg  commented on Jan. 5, 2018, 7:36 p.m.

      Given that there are at most 10000 cities, a matrix of integers would take up around 400 MB of memory, which is over the memory limit. You should instead find an alternative way to store the graph.


  • 2
    Pleedoh  commented on Aug. 26, 2017, 3:46 a.m.

    Bi-directional edges right?


    • 1
      Kirito  commented on Aug. 26, 2017, 2:41 p.m.

      Yes.


  • 8
    kobortor  commented on Feb. 18, 2017, 1:42 a.m.

    Because of a nearly identical problem, this point value of this problem has been adjusted to 12 pts.


  • -7
    xXxP0t4t0MStRxXx  commented on May 20, 2016, 2:24 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 9
      kobortor  commented on May 20, 2016, 2:55 a.m.

      It means your program crashed. It's probably because your array is 10000*10000 when the question has up to 100000 cities.


  • 3
    ThreeInches  commented on May 27, 2015, 2:07 p.m.

    I'm getting invalid return for the sixth test case. Using the test case from wcipeg, my answer is correct


    • 0
      quantum  commented on May 27, 2015, 10:15 p.m.

      I think you ran out of memory and the runtime exited with an exception.