SafeReturn
SRM 539 · 2011-11-22 · by vexorian
SRM 539 · 2011-11-22 · by vexorian · Graph Theory
Problem Statement
Problem Statement
You used to worry about your popularity with the troops, but not anymore. Your priority is their safety. You are the commander of N soldiers. Each soldier has an assignment to visit a different fort. They all leave fort 0 at the same time and travel through the streets of the city at the same time until each reaches his assigned destination. This is very risky and you would want each soldier to to reach his fort as soon as possible. It is also very dangerous to go alone, thus as a secondary objective, you must minimize the number of soldiers that are exposed to risk by going over at least one street alone.
There are T locations, where T >= N+1. The locations are numbered 0 to T-1. Location 0 is the fort where all soldiers start at time 0. For each i between 1 and N, inclusive, location i is the destination fort for one of the soldiers. The remaining locations have no specific meaning. Some pairs of locations are connected by bidirectional streets. The streets are given as aString[] streets. If there is no street connecting locations i and j, streets[i][j] will be '-' (quotes for clarity). Otherwise, streets[i][j] will be a digit between '1' and '9', inclusive. The digit represents the number of minutes it takes any soldier to walk along the street in either direction.
All soldiers can move at the same time, and multiple soldiers can move along the same street. If a group of soldiers reaches a fort that is the destination for one of them, that soldier enters the fort in zero time and the remaining ones keep on walking to other locations.
A soldier is safe if at each moment of his walk through the city he is accompanied by at least one other soldier. A soldier is endangered if he is not safe, i.e., if he walks alone for some time. Remember that the primary requirement is that each soldier must use one of the (possibly many) fastest paths to his destination fort. Given this requirement, you want to choose the paths in such a way that the number of soldiers in danger is minimized. Return the smallest possible number of endangered soldiers.
There are T locations, where T >= N+1. The locations are numbered 0 to T-1. Location 0 is the fort where all soldiers start at time 0. For each i between 1 and N, inclusive, location i is the destination fort for one of the soldiers. The remaining locations have no specific meaning. Some pairs of locations are connected by bidirectional streets. The streets are given as a
All soldiers can move at the same time, and multiple soldiers can move along the same street. If a group of soldiers reaches a fort that is the destination for one of them, that soldier enters the fort in zero time and the remaining ones keep on walking to other locations.
A soldier is safe if at each moment of his walk through the city he is accompanied by at least one other soldier. A soldier is endangered if he is not safe, i.e., if he walks alone for some time. Remember that the primary requirement is that each soldier must use one of the (possibly many) fastest paths to his destination fort. Given this requirement, you want to choose the paths in such a way that the number of soldiers in danger is minimized. Return the smallest possible number of endangered soldiers.
Constraints
- N will be between 1 and 49, inclusive.
- streets will contain T elements, where T is between N+1 and 50, inclusive.
- Each element of streets will contain T characters.
- Each character in each element of streets will either be '-', or one of '1'-'9'.
- For each i, streets[i][i] will be '-'.
- For each pair (i,j), streets[i][j] will be equal to streets[j][i].
- For each 1 <= i <= N, there will always be at least one way of reaching location i from location 0 by using one or more streets.
Examples
0)
3
{"-234",
"2---",
"3---",
"4---"}
Returns: 3
There are 3 soldiers assigned to 3 forts and 3 direct connections going from the starting fort to each of them. It is not possible for a soldier to accompany any other without losing the opportunity to reach his own fort in the minimum time possible.
1)
2
{"-12",
"1-1",
"21-"}
Returns: 1
The minimum time after which soldier #1 can reach fort is 1 minute and the minimum time for soldier #2 is 2 minutes. It is possible for soldier #2 to first drop soldier #1 off in his assigned fort before reaching his own one and both soldiers still reach their assigned fort in the minimum time.
2)
3
{"-----7",
"--1---",
"-1-5--",
"--5-1-",
"---1-3",
"7---3-"}
Returns: 1
3)
2
{"-11",
"1-1",
"11-"}
Returns: 2
4)
49
{"-2856935949296363317296813947187981785927784463848","2-751231576449966852481499753571157837382384523139","87-95652334996559687197545792475478858551432853657","559-6636992228434959593387784772921281748452833362","6156-914479312256161975832213195958412992619811252","92669-22433753466579789528319258138374484275441928","335312-8885129213115875849151222631857952239511567","5126428-522447348188687362778975831721572759128194","95394485-38917974538294224258733169533722954864687","473973823-4663678769262785952192787354219597891522","9642935284-143767681957817496887421269931833279462","24923714961-27996648936152261527228859116675586266","949215241642-3623362798284594661952816726734473231","6968239773373-422376668568767147911714747187774272","39542423967964-56465852822112642166169797832938851","665356147769225-3634115923668176844317244713156943","3694663848763263-652928788628515673983995426413412","38691511576633466-76776955516462349259268236948337","158567183684676357-2573315977519318715966523294599","7279195889182654262-166527965667387857714787879213","24159786229976819751-76822943652136777792838634946","989978789653965127767-9431641738999522169578669822","6173595742768825863669-849358782743411758559484716","84538583278125897935848-78443988213527845991958941","194832462815862285122347-6336787473412167454189219","3957289245724823855721986-883293163291617249249553","97772317294257166599963438-61447236983369777199716","459811575596961621764454386-1611133512429168217919","7324391882614728867531836311-545752594495455199195","15471229718561615456677972465-68477972723457876794","877795273982644716165388894146-2375755134414937736","7152582532771726529728287371582-396137285235921951","91499168174299186333197241217433-28572925989494629","857253336822516474183941763357792-1613287111318734","1781881197182164398769333363275681-443228614122323","78824387532887139278754542955971564-39293516247758","835817523565116185157212198197537143-8883714676844","5781247134996497395772172132425723398-619736262769","93579495729177729297717816344712922286-23719739732","285498572131249496619654616292382829812-4813149595","7218242229166774586429857799534557833934-614524989","73446227958671874257855942714442916577786-14376843","883517355937383123283759547655138111131111-6534799","4422959947354723663788914978574591464693446-961386","45888451882547914928664912121899431262715359-35994","625314126978773514973685849197329124763427363-5924","3333111841963486384949489997967148276299464155-319","81632951654222894352987925791779673787759873993-76","435652698266375413914214151199352325463984989217-2","8972287472261213279362619369546194384925939644962-"}
Returns: 26
Submissions are judged against all 185 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SafeReturn with a public method int minRisk(int N, vector<string> streets) · 185 test cases · 2 s / 256 MB per case