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?
9999
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 10 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.