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
Comments
What is the highest value can be?
10000
This comment is hidden due to too much negative feedback. Show it anyway.
:( 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.
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.
Bi-directional edges right?
Yes.
Because of a nearly identical problem, this point value of this problem has been adjusted to 12 pts.
This comment is hidden due to too much negative feedback. Show it anyway.
It means your program crashed. It's probably because your array is 10000*10000 when the question has up to 100000 cities.
I'm getting invalid return for the sixth test case. Using the test case from wcipeg, my answer is correct
I think you ran out of memory and the runtime exited with an exception.