## CCC '03 S5 - Trucking Troubles

View as PDF

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 to .

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: , and specifying the number of cities (in total), number of roads between cities and number of destination cities, respectively. The cities are numbered from to . There are at most cities and at most roads. The next lines contain triples indicating that this road runs between city and city and it has a maximum weight capacity of . The next 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 and that city is not a destination city. You can visit the destination cities in any order, but you must visit all destination cities.

The output from your program is a single integer, the largest weight that can be driven through all 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

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

What is the highest value can be?

• commented on Feb. 20, 2023, 1:31 a.m. edited

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

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

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

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

Bi-directional edges right?

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

Yes.

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

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

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

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

• 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

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

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