Time Limit: Java: 2000 ms / Others: 2000 ms
Memory Limit: Java: 65536 KB / Others: 65536 KB
The Fire Department of New York (FDNY) has always been proud of their response
time to fires in New York City, but they want to make their response time even
better. To help them with their response time, they want to make sure that the
dispatchers know the closest firehouse to any address in the city. You have
been hired to write this software and are entrusted with maintaining the proud
tradition of FDNY. Conceptually, the software will be given the address of the
fire, the locations of the firehouses, street intersections, and the time it
takes to cover the distance between each intersection. It will then use this
information to calculate how long it takes to reach an address from each firehouse.
Given a specific fire location in the city, the software will calculate the time taken from all the fire stations located in the city to reach the fire location. The list of fire stations will be sorted from shortest time to longest time. The dispatcher can then pick the closest firestation with available firefighters and equipment to dispatch to the fire.
This problem contains multiple test cases!
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
1 6 0 3 4 -1 -1 -1 -1 0 4 5 -1 -1 2 3 0 -1 -1 2 8 9 5 0 1 -1 7 2 1 -1 0 -1 5 -1 4 5 4 0 2 4 5 6 In the above input the last line indicates that ��2�� is the location of the fire and ��4��, ��5�� and ��6�� are the intersections where fire stations are located.