NordicOI 2024 T1

Question

题目描述
题目译自 NordicOI 2024 T1 「Anime Shops」

有 n 个城市和 m 条道路。每条道路都是双向的，连接了两个城市。已知有 k 个城市有动漫商店。

如果你住在某个城市，那你必然很了解本地的动漫商店。你想找到除了你的城市以外，离你所在的城市最近的动漫商店。

对于每个城市，确定到另一个有动漫商店的城市的最小距离。

输入格式
第一行有三个整数 n, m, k，分别表示城市、道路和动漫商店的数量。城市编号为 1,2,\dots,n。

第二行包含 k 个整数，表示有动漫商店的城市。

接下来的 m 行每行有两个整数 a 和 b，表示城市 a 和 b 之间有一条道路。

输出格式
输出 n 个整数，表示对于每个城市，到另一个有动漫商店的城市的最小距离。如果没有这样的城市，则输出 -1。

样例
输入
9 6 4
2 4 5 7
1 2
1 3
1 8
2 4
3 4
5 6
输出
1 1 1 1 -1 1 -1 2 -1

Answer 1

该回答引用自GPT-deepseek, 由博主 GISer Liu 编写：

问题分析

题目要求我们为每个城市找到离它最近的动漫商店所在的城市的最小距离。如果有多个动漫商店，我们需要找到距离最近的那个。如果某个城市没有连接到任何动漫商店，则输出 -1。

解决思路

1. 图的表示：我们可以使用邻接表来表示城市和道路之间的关系。邻接表是一种常见的图表示方法，适合处理稀疏图。

2. 广度优先搜索（BFS）：由于我们需要找到每个城市到最近的动漫商店的最小距离，BFS 是一个合适的选择。BFS 从起点开始，逐层扩展，可以保证第一次到达目标节点时的路径是最短的。

3. 多源 BFS：由于有多个动漫商店，我们可以将所有的动漫商店作为起点，同时进行 BFS。这样可以一次性计算出所有城市到最近的动漫商店的距离。

代码大纲

1. 输入处理：

   • 读取城市数量 n，道路数量 m，动漫商店数量 k。
   • 读取有动漫商店的城市列表。
   • 读取道路信息并构建邻接表。

2. 多源 BFS：

   • 初始化距离数组 dist，所有城市初始距离为 -1。
   • 将所有有动漫商店的城市加入队列，并将它们的距离设为 0。
   • 使用 BFS 遍历图，更新每个城市的最小距离。

3. 输出结果：

   • 输出每个城市的最小距离。

具体代码实现

from collections import deque

def main():
    # 输入处理
    n, m, k = map(int, input().split())
    anime_shops = list(map(int, input().split()))
    
    # 构建邻接表
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)
    
    # 初始化距离数组
    dist = [-1] * (n + 1)
    
    # 多源 BFS 初始化
    queue = deque()
    for shop in anime_shops:
        dist[shop] = 0
        queue.append(shop)
    
    # 执行 BFS
    while queue:
        current = queue.popleft()
        for neighbor in adj[current]:
            if dist[neighbor] == -1:
                dist[neighbor] = dist[current] + 1
                queue.append(neighbor)
    
    # 输出结果
    for i in range(1, n + 1):
        print(dist[i], end=' ')
    print()

if __name__ == "__main__":
    main()

代码解释

1. 输入处理：

   • 读取城市数量 n，道路数量 m，动漫商店数量 k。
   • 读取有动漫商店的城市列表 anime_shops。
   • 读取道路信息并构建邻接表 adj。

2. 多源 BFS：

   • 初始化距离数组 dist，所有城市初始距离为 -1。
   • 将所有有动漫商店的城市加入队列，并将它们的距离设为 0。
   • 使用 BFS 遍历图，更新每个城市的最小距离。

3. 输出结果：

   • 输出每个城市的最小距离。

样例输入输出

输入：

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

输出：

1 1 1 1 -1 1 -1 2 -1

复杂度分析

• 时间复杂度：O(n + m)，其中 n 是城市数量，m 是道路数量。BFS 的时间复杂度为 O(V + E)，其中 V 是顶点数，E 是边数。
• 空间复杂度：O(n + m)，用于存储邻接表和距离数组。

总结

通过多源 BFS，我们可以高效地计算出每个城市到最近的动漫商店的最小距离。这种方法在时间和空间上都是最优的，适合处理大规模的城市和道路数据。

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑