next up previous
Next: Thread Partitioning Up: UMD HPC98 Questions Previous: String Similarity

Campaign Trip Planning

As a presidential candidate, you need to cover the most territory in the least amount of time, blazing through miles of backwoods America on your way from one big city to another in an effort drum up enough support to win the election and make the massive amounts of money you showered on your campaign ads! Your staff is competent enough to find out what cities are connected to what others and how much time you are likely to have to spend traveling both within and between the cities, but they aren't quite competent enough to figure out what the best way for you to go would be.

However, since you've been well educated in the ways of data structures and algorithms, you are wise about these sorts of things. You know programming. To circumvent your staff, you decide to take matters into your own hands and write a program to find the shortest routes between two cities between which you need to travel, including time spent in all the cities on the route. Beware, it may not always be possible to travel from city 1 to city n.

Good luck with the campaign!

Input Format

The first line of input will be n, the number of cities. The second line will be n integers showing the delay for city tex2html_wrap_inline392 . During the trip, delays apply to cities 1 and n as well as all intermediate cities. The remaining lines with be a list of ordered triples (x,y,d) indicating a path from city x to city y with delay d. You may also travel from city y to city x with the same delay. All delays are integers. The end of the list will be a triple where x = 0.

Your goal is to find the quickest time to get from city 1 to city n. You do not have to visit all cities. You may assume all delays within a city or between cities will be less than or equal to 100, and the maximum number of cities is 100.

Output Format

The output consists of two lines. If no path exists from city 1 to city n, output ``No path found". Otherwise, on the first line output ``Shortest time: " and the shortest time from city 1 to city n. On the second line output ``Shortest path: ", followed by the list of cities on the shortest path in the order visitied, starting from city 1 and ending at city n. If there are multiple shortest paths, you may output any such path.

Examples

tex2html_wrap424 Input:

3
10 20 30
1 2 1
2 3 3
3 1 2
0 0 0

Output:

Shortest time: 42
Shortest path: 1 3

Input:

6
2 12 15 5 8 3
1 2 23
1 3 91
3 2 12
6 4 21
6 5 12
4 5 13
0 0 0

Output:

No path found

Test data used in judging

Input 1 Output 1
Input 2 Output 2
Input 3 Output 3
Input 4 Output 4
Input 5 Output 5
Input 6 Output 6
Input 7 Output 7
Input 8 Output 8

Our solution


next up previous
Next: Thread Partitioning Up: UMD HPC98 Questions Previous: String Similarity

Chau-Wen Tseng
Tue Mar 24 16:22:12 EST 1998