AirlineTravelPlanner | Topcoder Archive

Problem Statement

You are planning some airline travel. Direct flights are offered between several cities, but not necessarily between every pair of cities. Each flight that is offered takes a certain travel distance. Your goal is to find the shortest total distance possible, using any number of connecting flights, to get from start city to end city.

You are also given the distances for each available flight, in String[] dist. For each element i, the character j indicates the distance travelled from city i to city j. A distance of 0 means there is no flight available in that direction between those two cities. Note that the distance may not be the same in both directions.

Return the minimum distance travelled from city start to city end. If it is not possible to make such a trip, return -1.

Definition

Class:: AirlineTravelPlanner
Method:: shortestDistance
Parameters:: int, int, String[]
Returns:: int
Method signature:: int shortestDistance(int start, int end, String[] dist)
(be sure your method is public)

Constraints

start and end will be between 0 and Size(dist) - 1, inclusive.
start and end will be different.
dist will contain between 2 and 20 elements, inclusive.
Each element of dist will be the same length as the number of elements in dist.
Each character in each element of dist will be '0'-'9', inclusive.
Each character i of element i of dist will be '0'.

Examples

```
0
```
```
1
```
```
{"03",
 "20"}
```
```
Returns: 3
```
There's only one path to take, starting from point 0 and going to point 1, and it's a distance of 3. Notice that if we had gone the other way, it would have been shorter.
```
0
```
```
2
```
```
{"015",
 "201",
 "320"}
```
```
Returns: 2
```
Here, we could go directly from 0->2, which would be a distance of 5. However, it's shorter to go 0->1->2, for a distance of 1 + 1 = 2.
```
2
```
```
0
```
```
{"015",
 "201",
 "320"}
```
```
Returns: 3
```
In this case, though, a straight path from 2->0 is actually shorter than going 2->1->0.
```
0
```
```
2
```
```
{"010",
 "100",
 "320"}
```
```
Returns: -1
```
Although we can travel from city 2 to wherever we want, there's no way to get to city 2 if we start at city 0.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.