2003 Canadian Computing Competition, Stage 1

Problem S5: Trucking Troubles

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.

Input

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.

Output

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

Sample Output

30

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 27, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

My first code and AC code is not different at all. I searched the last data and ran in both programs, then I got the same output '0'. Please check this out.

Which two submissions are you talking about?

I mean my first WA submission and the last AC submission.

I confirm that the last test case is invalid, because the last test case says that city 1 is a destination city, but that is disallowed in the constraints.

Thanks for confirming the testcase:)

Fixed

I also rejudged all of dopa0509's submissions

the judge shows WA for the first two data sets though they return the right values on my computer. I had to hard code the first two to get them to pass. What's the problem?

Your program has undefined behaviour. See [url=http://wcipeg.com/wiki/Judge:Help#Execution_discrepancies]this[/url]. Whenever you make a non-global array, it is by default uninitialized and will very likely have garbage values in memory, so you'll need to initialize it first.

Thanks for the help! that was the problem

There are now up to 10000 cities and 100000 roads.
The point value will revert to 20, so no one will lose points.

range of 'd' ?

Since a limit on d isn't given, you can assume it can be as large as possible (namely, up to c).