Maximum Distance To Port

Key Idea

The port is fixed: city $1$. For every product type, we need the farthest city of that type, where distance means shortest path distance to city $1$.

That wording can make the problem sound like we need to run shortest paths separately for each product type. Nope. That would be unnecessary and potentially too slow. The graph distance from a city to the port does not depend on the product type. Products are just labels slapped onto cities after distances are known.

So we compute all distances to city $1$ once.

Why BFS?

Every road has length exactly $1$. In an unweighted graph, BFS from a source gives the shortest distance from that source to every node.

We run BFS starting from city $1$ and get:

$dist[v] =$ shortest distance from city $1$ to city $v$.

The graph is undirected, so the shortest distance from $1$ to $v$ is the same as from $v$ to $1$. Nice and boring, which is exactly what we want.

Computing The Answers

Let $a_i$ be the product type produced by city $i$.

After BFS, scan all cities:

$ans[a_i] = \max(ans[a_i], dist[i])$

That means for each product type, we keep the largest distance among all cities producing it.

Since every product type appears at least once, every answer will be filled naturally. Initializing answers to $0$ is fine because distances are never negative.

False Assumptions To Kill Immediately

• You do not need BFS from every product type.
• You do not need multi-source BFS.
• You do not need Dijkstra, because all edges have equal weight.
• You do not need to group cities by product first, though it would also work. A single final scan is cleaner.

Correctness Proof

We prove the algorithm outputs the required value for every product type.

First, BFS from city $1$ computes the shortest number of edges from city $1$ to every city $v$, because the graph is unweighted and BFS explores nodes in increasing distance order.

Since the graph is undirected, any path from $1$ to $v$ can be traversed backward as a path from $v$ to $1$ with the same length. Therefore, $dist[v]$ is also the shortest distance from city $v$ to the port.

For a product type $c$, the required answer is the maximum shortest distance to the port among all cities $v$ with $a_v = c$. The algorithm scans every city exactly once and updates $ans[c]$ with $dist[v]$ for each such city. Therefore, after the scan, $ans[c]$ is exactly the maximum required distance for product type $c$.

Thus, the algorithm is correct.

Complexity

Building the graph takes $O(n+m)$ memory and $O(m)$ time.

BFS takes $O(n+m)$ time.

The final scan takes $O(n)$ time.

Total complexity:

$O(n+m)$

Memory complexity:

$O(n+m)$