TaxiManager

SRM 347 · 2007-05-01 · by StevieT

SRM 347 · 2007-05-01 · by StevieT · Dynamic Programming, Search

Show categories

Class Name: TaxiManager

Return Type: int

Method Name: schedule

Arg Types: (vector<string>, vector<string>)

Problem Statement

You are the manager of a small taxi firm with 2 cars. On a particular evening, you have a number of customers who wish to travel between various locations, and you have to decide how to schedule the trips. Both of your cars start out at your base at location 0, and as manager, you have to wait for both of the cars to return to base before you can leave work for the night. Your goal is to minimize the amount of time before all of the customers have been delivered to their destinations and the cars have both returned to location 0.

The area in which your customers want to travel is represented by M locations, indexed from 0 to M-1, some of which are connected by roads. You will be given a String[] roads, where the j-th digit of the i-th element is the time to travel on the direct road from location i to location j, or '0' if no direct route between these locations exists. You will also be given a String[] customers, where each element contains two space-separated integers that represent the indices of the starting location and destination of a customer. Customers have no preference as to which car picks them up and you may schedule the customers in any order, but once a car has picked up a customer, it must take him or her immediately to the required destination; the customer cannot be dropped off at an intermediate location to be picked up again later. Customers will also not share a car with each other, so if a taxi is carrying a customer it may not pick up another one. Picking up or dropping off a customer takes negligible time.

You should return the minimum amount of time before both of your cars have returned to base and you can go home for the night.

Notes

roads will not necessarily be symmetric. Therefore the time taken to drive from location i to j may not be the same as the time to drive from j to i.

Constraints

roads will contain between 2 and 50 elements, inclusive.
Each element of roads will contain exactly M characters, where M is the number of elements in roads.
Each character in roads will be a digit ('0' - '9').
The i-th character in the i-th element of roads will be '0'.
Each location will be reachable from all other locations.
customers will contain between 1 and 12 elements, inclusive.
Each element in customers will contain 2 distinct space-separated integers.
Each integer in customers will be between 0 and M-1, inclusive, with no leading zeros.

Examples

{"020200"
,"202020"
,"020002"
,"200020"
,"020202"
,"002020"}
{"5 3","2 4","1 5","3 2"}
Returns: 16

An example of an optimal schedule is: Time Action 0 Car 1 - Drive to location 3 0 Car 2 - Drive to location 1 2 Car 1 - Pick up customer 3, then drive to location 0, then 1, then 2 2 Car 2 - Pick up customer 2, then drive to location 2, then 5 6 Car 2 - Drop off customer 2, pick up customer 0, then drive to location 4, then 3 8 Car 1 - Drop off customer 3, pick up customer 1, then drive to location 1, then 4 10 Car 2 - Drop off customer 0, then drive to location 0 12 Car 2 - Arrive back at base 12 Car 1 - Drop off customer 1, then drive to location 1, then 0 16 Car 1 - Arrive back at base

{"00020251090265906661"
,"00763002550100090081"
,"06003699000080062771"
,"00000710460400035310"
,"50000039119198350060"
,"66060004050810046028"
,"02333108565000200880"
,"40212560000209205231"
,"02601150098329905062"
,"00210383709951005203"
,"10111087340780827070"
,"05065800003095040140"
,"15604020082000100090"
,"83430030070580600750"
,"10588355007006001150"
,"14400080790005400536"
,"23400990400933060004"
,"11053016300602000090"
,"90040920084059282502"
,"61300007077904050900"}
{"0 19","4 16","15 16","4 18","2 7","9 15","11 6","7 13","19 13","12 19","14 12","16 1"}
Returns: 33

{"095222800320504"
,"107600288090501"
,"760973530769345"
,"963093337510830"
,"338404069255826"
,"291700050155264"
,"002783031709004"
,"404730701707712"
,"068870030090995"
,"320025180036103"
,"468695042801904"
,"233626561000105"
,"070014432197086"
,"887301000143802"
,"230852749990330"}
{"3 6","0 4","2 7","9 7","13 9","1 6","7 13","14 2","8 7","10 1","11 13","7 12"}
Returns: 28

{"00401","50990","00062","08008","03000"}
{"2 4"}
Returns: 14

With only one customer, you only need to send out one car.

{"02002507209006769080003000000038710008270075752100","70005000440300400058500002000487012560037200700206","01009002000960002190090007600013701009090042752001","60508022900009076080005000600000000060009122001660","00000000000007000000068217000448002066200062060040","76090003670040056900070760002006000002732008008662","78530304800200090010020300426004600250190765017000","00050000740800355020009480434409800000035000676071","06600400065795008040500111800000050906003300900520","71800609805419030000600046000008273000800000003100","00940000450000000009703000080270000137000403640817","06086340050070051402000900408038083000500000407073","36027950000000900050500008630000000300013001000772","50096070205800900200901100670001005801000206000637","70250002000067000205000800100556010000099000203800","00900600600003000040000602051720120018375030000955","60770700002800000300830603081074009301620304000700","00700000001003004010000809640255777020008535006055","00900609090001090000700900690060000072300050099402","00010000896000306010000051285095009030400480200132","80580001000900360500000013000030802470270930700000","10000000200790900981004002201808760072050009080685","00109001008805900049950008001060000006130510600003","97900003250600004070008000060005600470001400016260","10050000409609000000600009104090006049250000080000","09000021480000007750400100800020060518923050700500","00007470005090001000010010063009800900801484000635","50496301200000010693802230000090000030987013201000","07001500006660600300627000900060286000000403880000","65030101560624438080202040090086050000000000413012","40610204023010087700000003000009003001403002080000","40200004000900260907050030340450000340095000950990","09600100050098490000101560000000068091009770000000","04003001040309374350040000000201907000476600603794","00072084000803002620520500890005800044550000400000","70607087710000097000500500000003200005900000000000","03509090000090300100800375000040000100560004007520","62000000010000702083040000109376000000000002645000","40050000056240000900063000034010200527001510000989","00032014900997003008200060596870000870007000113150","76007090004013800060200150002008104600090500020903","01860005000808002000020000940007035000518000030083","00000800000209990031004400000040090200004600700080","00135810000090040930110070009850700040538000000102","08700020270001404006094800402200949050210400044700","10709368100080300000220040026634005508708010006900","60620120000007005305020044000614006600568000000723","80009007090530310003004000627000040008003401006002","70000099001668800039970430083000058005301805907300","82848000006002008330000700005088602020007001800060"}
{"3 29","6 26","20 47","26 45","45 38","40 12","0 48","39 40","19 9","15 36","11 31"}
Returns: 31

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

Coding Area

Language: C++17 · define a public class TaxiManager with a public method int schedule(vector<string> roads, vector<string> customers) · 50 test cases · 2 s / 256 MB per case