Programming Contest

Problem 1: How many junctions?

Problem description:
The problem deals with the minimization of the path for a shipping problem. This problem deals with the delivery of large items where shipping becomes more complicated. When the path is larger, items are shipped from one city to another, and change shipping method at each location until they arrive to the wanted location. There are two costs related to transportation: 1- the cost of transportation between two cities and 2- the transshipping fees for any cargo passing through a city. A solution to this problem must find the shipping path with the least cost taking into consideration the two components of the transportation fee.

Description of input
The input consists of an integer m showing the number cases, followed for each case by the following:
- An integer n which is the degree of the matrix
- n lines holding costs describing the matrix
- A line of n integers giving the transshipping cost of each city
- A line of two integers which represent the source and the destination nodes.

Description of output
- The output shows the sequence of cities passed by and the total cost.

|Sample Input                                 |Sample Output                                 |
|                                             |                                               |
|2                                             |From 1 to 3:                                   |
|5                                             |Path: 1-->5-->4-->3                           |
|0 3 22 -1 4                                   |Total cost: 21                                 |
|3 0 5 -1 -1                                   |                                               |
|22 5 0 9 20                                   |From 1 to 3:                                   |
|-1 -1 9 0 4                                   |Path: 1-->2-->3                               |
|4 -1 20 4 0...