Implement a function with the following signature:
function costSavings(int $numCities, array $flights): intThe input describes the operational costs of an airline operating several flights
between a number of cities. For simplicity, cities are denoted by integer numbers
from 0 to flights array describes routes and costs in the
following format:
[
['from' => 0, 'to' => 1, 'cost' => 3],
['from' => 2, 'to' => 0, 'cost' => 1],
['from' => 2, 'to' => 3, 'cost' => 1],
['from' => 1, 'to' => 3, 'cost' => 2],
]Each array entry describes a single route between cities denoted by the indices in
the 'from' and 'to' fields. Operational costs are listed as a positive integer
number in the 'cost' field.
For simplicity, assume that all flights are bidirectional (so that the first
element of the array above describes both the flight from city 0 to city 1, and
the flight from city 1 to city 0). We will also assume that there are no shared
operational costs for different flights.
The airline claims that each of the cities it currently serves is reachable from
every other city that it also serves using only flights operated by this same
airline. (For example, given the input above, it's possible to get from city 0 to
city 3 first by taking a flight from city 0 to city 1, and then a flight from city
1 to city 3; using city 2 instead of city 1 as a layover point is also possible.)
However, the company wants to cut its operational costs while preserving this
property of every city being reachable from every other city. costSavings() should
compute the maximum possible savings for the airline.
Given the input above (with $numCities = 4), costSavings() should return 3 as a
result. The flight between cities 0 and 1 can be dropped, thus reducing the
operational costs by 3, and no other flight can be dropped after that.
If we use the following numCities = 4):
[
['from' => 0, 'to' => 1, 'cost' => 3],
['from' => 2, 'to' => 0, 'cost' => 1],
['from' => 2, 'to' => 3, 'cost' => 1],
['from' => 1, 'to' => 3, 'cost' => 2],
['from' => 2, 'to' => 1, 'cost' => 1],
]...costSavings() should return 5 as a result.
Note that there can be multiple flights connecting the same pair of cities, each
with its own operational costs. In that case, the airline would definitely want
to get rid of all of them except for the cheapest one (and perhaps it would be
economical to get rid of that one, too). E.g., with $numCities = 2:
[
['from' => 0, 'to' => 1, 'cost' => 3],
['from' => 1, 'to' => 0, 'cost' => 1],
['from' => 0, 'to' => 1, 'cost' => 2],
]...costSavings() should return 5.
In case the input array does not describe a set of routes that connect all the
cities, costSavings() should return -1 as a result. For example, calling
costSavings() with any of the above arrays, but $numCities = 5 should produce -1 as
a result. (Because there would be no flights connecting city 4 to any of the other
cities.)
All inputs are guaranteed to be valid, so you do not need to verify whether city
indices and operational costs lie within the bounds specified above.
You also do not need to concern yourself with issues of integer precision, all the
inputs supplied to your function will ensure that the final result and any
intermediate results fit into 64-bit integers.
From efficiency standpoint, your solution should be able to process a set of
flights connecting a couple of hundred cities, with each city being directly
connected to every other city, within no more than a few seconds