Connection Status:
Competition Arena > OnTime

OnTime

SRM 339 · 2007-02-14 · by _efer_

SRM 339 · 2007-02-14 · by _efer_ · Dynamic Programming, Search, String Parsing
Class Name: OnTime
Return Type: int
Method Name: minCost
Arg Types: (int, int, vector<string>)
Problem Statement

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.

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.

Submissions are judged against all 90 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class OnTime with a public method int minCost(int N, int T, vector<string> buses) · 90 test cases · 2 s / 256 MB per case

Submitting as anonymous