OnTime | Topcoder Archive

Problem Statement

Little Billy needs your help to get to school on time. There are N bus stations in Billy's town, numbered from 0 to N-1. His home is near station 0 and his school is near station N-1. There are several school buses, each connecting a single pair of stations. Billy has to take one or more of these buses to get to school.

You will be given a String[] buses describing each of the school buses. The i^th element of buses describes the i^th bus and will be formatted as "a b departure time cost", where a, b, departure, time and cost are integers. a and b denote the starting and ending stations, departure is the time when the bus leaves from station a, time gives the time the bus needs to get from a to b, and cost is the cost of a ticket for that bus. Billy starts at time 0 and must get to station N-1 in T or less minutes. Return the minimum amount of money he will need to spend on bus tickets to get to school on time. If Billy cannot make it on time, return -1. Note that Billy can't grab a bus departing from a station at the same time he arrived at that station, but can take a bus leaving station 0 at time 0.

Definition

Class:: OnTime
Method:: minCost
Parameters:: int, int, String[]
Returns:: int
Method signature:: int minCost(int N, int T, String[] buses)
(be sure your method is public)

Constraints

N will be between 2 and 50, inclusive.
T will be between 1 and 10,000, inclusive.
buses will contain between 1 and 50 elements, inclusive.
Each element of buses will contain between 9 and 50 characters, inclusive.
Each element of buses will be formatted as "a b departure time cost".
In each element of buses, a and b will be distinct integers between 0 and N-1, inclusive.
In each element of buses, departure will be an integer between 0 and 10,000, inclusive.
In each element of buses, time will be an integer between 1 and 10,000, inclusive.
In each element of buses, cost will be an integer between 1 and 1,000,000, inclusive.
Each number in each element of buses will contain no leading zeroes.
Each element of buses will contain no leading or trailing spaces.

Examples

```
3
```
```
8
```
```
{"0 1 0 4 3", "1 2 5 3 4"}
```
```
Returns: 7
```
Billy must take the first bus from station 0 at time 0 and then the second bus at time 5 from station 1, and will arrive just in time.
```
3
```
```
8
```
```
{"0 1 0 4 3", "1 2 6 3 4"}
```
```
Returns: -1
```
This time the second bus arrives just a minute too late.
```
3
```
```
7
```
```
{"0 1 0 5 1", "1 2 6 1 40", "0 1 1 2 5", "1 2 4 2 5"}
```
```
Returns: 10
```
If Billy takes the cheapest bus, he will then have to take the very expensive second bus. It turns out it is better to take the last two buses instead.
```
3
```
```
8
```
```
{"0 1 0 5 3", "1 2 5 3 4"}
```
```
Returns: -1
```
Billy arrives at station 1 at time 5, so he cannot take the second bus.
```
3
```
```
100
```
```
{"0 1 0 1 1"}
```
```
Returns: -1
```
With plenty of free time, Billy will have to walk to school since the only bus doesn't take him to the station near his school.

{"0 3 1 6 15", "0 6 0 23 20", "6 2 25 15 30", "6 1 30 15 40", "3 1 15 35 10", 
 "3 2 30 80 40", "1 5 55 25 25", "1 2 49 31 10", "2 8 85 10 10", "5 8 83 15 5"}

Returns: 55

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.