Hi, I'm writing a programming competition tomorrow (yikes!), and was just wondering about a common type of problem that always seems to show up. I can *kind* of get my head around it, but not fully. This is not homework, and I'm allowed to bring in any materials I choose to the contest.
Basically, the problem looks like this:
Quote:
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 100000.
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 1000 cities and at most 10000 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.
|
I understand what it's asking for, I'm just not quite sure on the correct method to do it. I don't need code, but a general push in the right direction will be very useful.
I'll post what I've figured out so far (it might be completely wrong)
Set up some sort of linked list representing the cities. Each node in the linked list will contain (in addition to the *next pointer), an array of pointers to other nodes. These will be matched with an array of integers, representing the greatest amount of weight going from one city to the next.
I know that can represent the data, but it doesn't seem like a very efficient way to do so (we are also marked on efficiency). However, I am unaware of any structures that could fit this type of problem better (or maybe I'm just not seeing it correctly). I also can't figure out how to properly traverse that linked list so as to find the greatest weight to be driven thru all cities.
Here is a sample input/output:
Quote:
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
|