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 ith element of buses describes the ith 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 |
| 0) | |
| | 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. |
|
|
| 1) | |
| | 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. |
|
|
| 2) | |
| | 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) | |
| | 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. |
|
|
| 4) | |
| | | 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. |
|
|
| 5) | |
| | 9 | 100 | {"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 | |
|