Program / Task Name:

   Data Transmission

Level:

 

 Novice / Advanced

Point Value:

 

 10

 

Task Description

In this problem your task is to find the quickest path for information to flow from a source city to a destination city.  The transmission can start from any city and end up at any city.  Your task is to always find the fastest based on the transmission times between cities. 

Data transmission mapUsing the map at right, you will be given a set of values for each of the numbered links, followed by a start city and destination city. Your challenge is to always find the quickest path for the data and display the cities as the data travels through them.  Each of the lettered links will be a transmission time.  (A = 1 second, B = 2 seconds, etc….)

 

Program Input

Your program will read in the link times from “A” to “K” and a series of source and destination cities from prob10.in.  The first line will be the link time for link “A”, and the 11th line will be the link time for link “K”.  The lines following those will be source city followed by a space and the destination city.

5
10
2
6
4
1
1
3
2
2
5
SEA HOU
NYC LA
CHI SEA
PHX HOU

Program Output

Output to the screen the trip title, the cities traveled through, including start and destination and the total transmission time (from start to destination).

For SEA to HOU: SEA, LIN, ATL, HOU in 5 seconds
For NYC to LA:  NYC, LIN, PHX, LA in 10 seconds
For CHI to SEA:  CHI, NYC, LIN, SEA  in 7 seconds
For PHX to HOU:  PHX, HOU in 2 seconds

 

 

   
  (c) 2004 Hewlett-Packard Company