FastPrep
Problem · Graph

Best Telescope Site

Learn this problem
● HardAtlassian logoAtlassianFULLTIMEOA

Problem statement

There are cityNodes cities numbered from 1 to cityNodes. The arrays cityFrom, cityTo, and cityWeight describe weighted bidirectional edges of a connected graph.

For each city, count the other cities whose shortest-path distance is at most distanceThreshold. Return the city with the smallest count. If several cities tie, return the highest city number.

Function

bestTelescopeSite(cityNodes: int, cityFrom: int[], cityTo: int[], cityWeight: int[], distanceThreshold: int) → int

Examples

Example 1

cityNodes = 3cityFrom = [1,2]cityTo = [2,3]cityWeight = [3,1]distanceThreshold = 3return = 3

Cities 1 and 3 each reach one other city within the threshold; the higher-numbered city 3 wins the tie.

Constraints

  • 2 <= cityNodes <= 100
  • 1 <= cityFrom.length <= 10000
  • 1 <= cityWeight[i], distanceThreshold <= 10^9
  • The graph is connected.

More Atlassian problems

drafts saved locally
public int bestTelescopeSite(int cityNodes, int[] cityFrom, int[] cityTo, int[] cityWeight, int distanceThreshold) {
  // Write your code here.
}
cityNodes3
cityFrom[1,2]
cityTo[2,3]
cityWeight[3,1]
distanceThreshold3
expected3
checking account