题解：P11591 [NordicOI 2024] Anime Shops

· · 题解

解析

如题，每个城市间有双向道路，所以我们可以使用无向带权图和搜索来解题。

用一个队列来实现图，并对这个图进行深度优先搜索，如果当前搜索的节点有动漫商店时，记录当前节点与起点城市的距离（即图之间的权值之和），与之前所记录的最小值进行比较，若该距离比之前所记录的最小值更小，则将最小值更新为当前距离，并返回上一个节点，进行搜索。最后输出最小值。

CODE

from collections import deque
def main():
    n, m, k = map(int, input().split())
    anime_cities = set(map(int, input().split()))
    graph = {i: [] for i in range(1, n + 1)}
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    results = []
    for start_city in range(1, n + 1):
        queue = deque([(start_city, 0)])
        visited = set([start_city])
        found = False
        min_distance = float('inf')
        while queue:
            current_city, distance = queue.popleft()
            if current_city in anime_cities and current_city!= start_city:
                min_distance = distance
                found = True
                break
            for neighbor in graph[current_city]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, distance + 1))
        if found:
            results.append(min_distance)
        else:
            results.append(-1)
    print(*results)
if __name__ == "__main__":
    main()