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)

 `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.
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`

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7423

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10663&pm=7423

_efer_

Testers:

PabloGilberto , brett1479 , radeye , Olexiy

Problem categories:

Dynamic Programming, Search, String Parsing