CCC '03 S5 - Trucking Troubles

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 64M

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.

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
    ht2012  commented on Jan. 5, 2018, 5: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.


    • 0
      wleung_bvg  commented on Jan. 5, 2018, 2: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.


  • 0
    Pleedoh  commented on Aug. 25, 2017, 11:46 p.m.

    Bi-directional edges right?


    • 0
      Kirito  commented on Aug. 26, 2017, 10:41 a.m.

      Yes.


  • 0
    Ninjaclasher  commented on May 28, 2017, 11:37 a.m.

    Can I have a hint on if my approach to the problem is correct?


  • 8
    kobortor  commented on Feb. 17, 2017, 8:42 p.m.

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


    • 1
      Kirito  commented on Feb. 17, 2017, 9:19 p.m.

      At least rescore all the old submissions


      • 4
        kobortor  commented on Feb. 17, 2017, 11:03 p.m.

        I dont have perms plz help


  • -2
    xXxP0t4t0MStRxXx  commented on May 19, 2016, 10:24 p.m.

    \[None\]where can i find info on RTE (Segmentation fault)?????\[None\]


    • 8
      kobortor  commented on May 19, 2016, 10:55 p.m.

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


  • -27
    ThreeInches  commented on June 1, 2015, 12:47 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 25
      BMP  commented on June 1, 2015, 2:56 p.m. edited

      you hardcoded it wrong?


      • 31
        kobortor  commented on June 1, 2015, 9:40 p.m.

        It's sad that c++ is faster to calculate the answer than for c# to print hard coded answers.


  • 3
    ThreeInches  commented on May 27, 2015, 10:07 a.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, 6:15 p.m.

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