← 返回题目列表

Codeforces · 2172/M

M. 到端口的最大距离

中文机器翻译题面 查看原题

有 $$$n$$$ 个城市,编号从 $$$1$$$ 到 $$$n$$$,由 $$$m$$$ 双向道路连接,每条道路正好 $$$1$$$ 公里长。道路网络形成一个连接的简单图。

每个城市只生产 $$$k$$$ 类型的农产品中的一种,编号从 $$$1$$$ 到 $$$k$$$。城市 $$$1$$$ 是所有产品必须交付的主要港口。

政府希望估算出口农产品的最坏情况运输成本和时间。为了实现这一目标,他们需要针对每种产品类型确定从生产该产品的任何城市到港口城市的最短距离(以公里为单位)中最长的距离。

您的任务是计算每种产品类型的最大最短距离。

图 1:示例输入 2 的图示。

输入

第一行包含三个整数$$$n$$$、$$$m$$$和$$$k$$$,分别代表城市数量、双向道路数量和产品类型。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$,其中 $$$a_i$$$ 是城市 $$$i$$$ 生产的产品类型。

接下来的$$$m$$$行中的第$$$i$$$行包含两个整数$$$u_i$$$和$$$v_i$$$,表示第$$$i$$$双向道路连接城市$$$u_i$$$和$$$v_i$$$。

  • $$$1 \leq n \leq 2 \times 10^{5}$$$
  • $$$0 \leq m \leq 2 \times 10^{5}$$$
  • $$$1 \leq k \leq n$$$
  • $$$1 \leq a_i \leq k$$$
  • $$$1 \leq u_i, v_i \leq n$$$
  • 该图是连通且简单的(无自环或多边)。
  • 从 $$$1$$$ 到 $$$k$$$ 的每种产品类型至少由一个城市生产。

输出

在一行中输出 $$$k$$$ 个整数。第 $$$i$$$ 个整数应该是从任何生产产品 $$$i$$$ 的城市到港口城市 $$$1$$$ 的最大最短距离(以公里为单位)。

示例

输入
复制

3 3 2
2 1 1
1 2
3 1
3 2

输出
复制

1 0

输入
复制

8 10 5
5 1 1 2 4 4 2 3
8 2
4 6
6 2
5 2
2 7
8 6
1 2
7 6
3 1
1 5

输出
复制

1 3 2 2 0

注意

例2说明: 图 1 说明了此示例。在此示例中,端口是蓝色节点。产品类型 5 的所有货物均已到达港口,因此其运输成本为 0。产品类型 4 的运输成本较高。产品类型为 4 的一个城市到港口的距离为 1,而另一个城市到港口的距离为 2。因此,运输成本为 2。