FastPrep
Problem · Graph

Delivery Management System

Learn this problem
● MediumAkuna Capital logoAkuna CapitalINTERNOA

Problem statement

A manufacturing company needs to ship goods to cities connected by bidirectional roads.

Determine the order of cities for delivery based on these rules:

  • Cities are numbered from 1 to cityNodes.
  • Some cities might be inaccessible due to lack of connecting roads.
  • Delivery order is determined first by distance from the manufacturing company.
  • If multiple cities are at the same distance, prioritize the city with the smaller number.

Complete the function order with the following parameters:

  • int cityNodes: the number of cities
  • int cityFrom[n]: the first city node where there is a bidirectional edge
  • int cityTo[n]: the second city node where there is a bidirectional edge
  • int company: the node where the route starts

Return an int[] containing the cities in the order visited.

Input Format for Custom Testing

The first line contains two space-separated integers: cityNodes, denoting the number of cities, and n, denoting the number of roads.

Each line i of the n subsequent lines, where 0 ≤ i < n, contains two space-separated integers, cityFrom[i] and cityTo[i].

The next line contains an integer, company.

Function

order(cityNodes: int, cityFrom: int[], cityTo: int[], company: int) → int[]

Examples

Example 1

cityNodes = 4cityFrom = [1, 2, 2]cityTo = [2, 3, 4]company = 1return = [2, 3, 4]

For example, say that the number of cities is cityNodes = 4, where cityFrom = [1, 2, 2], cityTo = [2, 3, 4], and company = 1. The company is located in city 1, and the roads run between cities 1 and 2, cities 2 and 3, and cities 2 and 4, like so:

1
2
3
4

In this case, the cities are visited based on the following logic:

  • The closest city (or cities) is visited first. This is city 2, which is 1 unit from the manufacturing company.
  • The next-closest cities are visited next. City 3 and city 4 are both 2 units from the company.
    • In this case, the lower-numbered city is prioritized: visit city 3 first, then city 4.

Therefore, the answer is [2, 3, 4].

Constraints

  • 2 ≤ cityNodes ≤ 10^5
  • 1 ≤ n ≤ min((cityNodes × (cityNodes - 1)) / 2, 10^5)
  • 1 ≤ cityFrom[i], cityTo[i], company ≤ cityNodes
  • cityFrom[i] ≠ cityTo[i]

More Akuna Capital problems

drafts saved locally
public int[] order(int cityNodes, int[] cityFrom, int[] cityTo, int company) {
  // write your code here
}
cityNodes4
cityFrom[1, 2, 2]
cityTo[2, 3, 4]
company1
expected[2, 3, 4]
checking account