Minimum Latency Server Path
Problem statement
Servers are identified by their IP address strings. The arrays fromServers, toServers and latencies describe directed links: link i goes from fromServers[i] to toServers[i] and takes latencies[i] milliseconds.
Return a path from startServer to endServer whose total latency is as small as possible. Return the addresses in travel order, including both endpoints.
Rules
- Every link has strictly positive latency. Parallel links and self-loops are allowed.
- If several paths have the same minimum total latency, return the lexicographically smallest sequence of address strings. Compare strings character by character, rather than comparing numeric IPv4 parts.
- If the destination is unreachable, return an empty array.
- If startServer equals endServer, return the one-element path containing that address.
Function
minimumLatencyPath(fromServers: String[], toServers: String[], latencies: int[], startServer: String, endServer: String) → String[]Examples
Example 1
fromServers = ["10.0.0.1","10.0.0.1","10.0.0.2","10.0.0.3"]toServers = ["10.0.0.3","10.0.0.2","10.0.0.3","10.0.0.4"]latencies = [9,2,3,1]startServer = "10.0.0.1"endServer = "10.0.0.4"return = ["10.0.0.1","10.0.0.2","10.0.0.3","10.0.0.4"]The path through 10.0.0.2 takes 2 + 3 + 1 = 6 milliseconds. Going directly from 10.0.0.1 to 10.0.0.3 and then to 10.0.0.4 takes 9 + 1 = 10 milliseconds.
Example 2
fromServers = ["10.0.0.1","10.0.0.1","10.0.0.10","10.0.0.2"]toServers = ["10.0.0.2","10.0.0.10","10.0.0.4","10.0.0.4"]latencies = [2,2,3,3]startServer = "10.0.0.1"endServer = "10.0.0.4"return = ["10.0.0.1","10.0.0.10","10.0.0.4"]Both routes take 5 milliseconds. The string 10.0.0.10 sorts before 10.0.0.2, so the path through 10.0.0.10 is returned.
Example 3
fromServers = ["10.0.0.1"]toServers = ["10.0.0.2"]latencies = [5]startServer = "10.0.0.2"endServer = "10.0.0.1"return = []The only link goes from 10.0.0.1 to 10.0.0.2. It cannot be traveled in reverse, so the destination is unreachable.
Constraints
- 0 <= fromServers.length <= 10000.
- fromServers, toServers and latencies have equal lengths.
- 1 <= latencies[i] <= 10^9.
- Every server address is a valid dotted-decimal IPv4 address with no leading zeros, of length 7 to 15.
- At most 500 distinct server addresses appear, including the start and end.