「NordicOI 2024」Anime Shops 题解

题目理解

我们需要为每个城市找到到最近的其他动漫商店的距离。关键点：

• 如果城市本身有动漫商店，需要找另一个商店
• 距离指的是最短路径长度
• 如果无法到达任何其他商店，输出-1

关键观察

1. 问题转化

这是一个多源最短路径问题：

• 所有动漫商店都是起点
• 对于没有商店的城市，直接找最近的商店
• 对于有商店的城市，需要找次近的商店（排除自身）

2. 算法选择

多源BFS是最佳选择：

• 所有商店同时作为起点开始BFS
• 第一次访问某个节点时记录的距离就是最短距离
• 时间复杂度 $O(n + m)$，适合大规模数据

算法思路

方法：多源BFS + 特殊处理

步骤1：初始化

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<vector<int>> adj(n + 1);
    vector<int> dist(n + 1, INF);  // 到最近商店的距离
    vector<int> from_shop(n + 1, -1); // 最近的商店是哪个
    vector<bool> is_shop(n + 1, false);
    queue<int> q;

步骤2：读取输入并初始化BFS

    // 读取动漫商店
    for (int i = 0; i < k; i++) {
        int shop;
        cin >> shop;
        is_shop[shop] = true;
        dist[shop] = 0;
        from_shop[shop] = shop;
        q.push(shop);
    }
    
    // 读取道路
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

步骤3：多源BFS

    // 多源BFS
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (dist[v] > dist[u] + 1) {
                dist[v] = dist[u] + 1;
                from_shop[v] = from_shop[u]; // 记录这个距离来自哪个商店
                q.push(v);
            }
        }
    }

步骤4：处理有商店的城市（需要找次近商店）

    // 对于有商店的城市，需要找次近的商店
    vector<int> second_dist(n + 1, INF);
    
    // 重新BFS，但跳过来自自身商店的路径
    for (int i = 1; i <= n; i++) {
        if (is_shop[i]) {
            queue<pair<int, int>> q2; // (节点, 距离)
            vector<bool> visited(n + 1, false);
            
            // 从邻居开始，跳过自身
            for (int neighbor : adj[i]) {
                if (from_shop[neighbor] != i) { // 不是来自自身商店的路径
                    second_dist[i] = min(second_dist[i], dist[neighbor] + 1);
                } else {
                    // 如果邻居的最近商店是自身，需要BFS找次近
                    q2.push({neighbor, 1});
                    visited[neighbor] = true;
                }
            }
            
            // BFS找次近商店
            while (!q2.empty()) {
                auto [u, d] = q2.front();
                q2.pop();
                
                if (from_shop[u] != i && is_shop[u]) {
                    second_dist[i] = min(second_dist[i], d);
                    continue;
                }
                
                for (int v : adj[u]) {
                    if (!visited[v] && v != i) {
                        visited[v] = true;
                        q2.push({v, d + 1});
                    }
                }
            }
        }
    }

步骤5：输出结果

    // 输出结果
    for (int i = 1; i <= n; i++) {
        if (is_shop[i]) {
            cout << (second_dist[i] == INF ? -1 : second_dist[i]) << " ";
        } else {
            cout << (dist[i] == INF ? -1 : dist[i]) << " ";
        }
    }
    
    return 0;
}

优化版本（更高效）

上面的方法对于有商店的城市进行了额外的BFS，可能较慢。下面是更优化的版本：

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, k;
    cin >> n >> m >> k;
    
    vector<vector<int>> adj(n + 1);
    vector<int> dist(n + 1, INF);
    vector<int> from_shop(n + 1, -1);
    vector<bool> is_shop(n + 1, false);
    vector<int> second_dist(n + 1, INF); // 次近距离
    
    // 读取商店
    for (int i = 0; i < k; i++) {
        int shop;
        cin >> shop;
        is_shop[shop] = true;
    }
    
    // 读取道路
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    // 第一次BFS：找到最近商店
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (is_shop[i]) {
            dist[i] = 0;
            from_shop[i] = i;
            q.push(i);
        }
    }
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (int v : adj[u]) {
            if (dist[v] > dist[u] + 1) {
                dist[v] = dist[u] + 1;
                from_shop[v] = from_shop[u];
                q.push(v);
            }
        }
    }
    
    // 第二次BFS：为有商店的城市找次近商店
    // 使用多源BFS，但排除自身商店的影响
    vector<int> temp_dist(n + 1, INF);
    queue<int> q2;
    
    for (int i = 1; i <= n; i++) {
        if (is_shop[i]) {
            // 从所有邻居开始，但排除来自自身商店的路径
            for (int neighbor : adj[i]) {
                if (from_shop[neighbor] != i) {
                    second_dist[i] = min(second_dist[i], dist[neighbor] + 1);
                } else {
                    // 这些邻居的最近商店是i，需要继续探索
                    if (temp_dist[neighbor] > 1) {
                        temp_dist[neighbor] = 1;
                        q2.push(neighbor);
                    }
                }
            }
        }
    }
    
    // BFS继续探索
    while (!q2.empty()) {
        int u = q2.front();
        q2.pop();
        
        for (int v : adj[u]) {
            if (temp_dist[v] > temp_dist[u] + 1) {
                temp_dist[v] = temp_dist[u] + 1;
                // 如果找到其他商店，更新次近距离
                if (is_shop[v] && from_shop[v] != from_shop[u]) {
                    for (int shop = 1; shop <= n; shop++) {
                        if (is_shop[shop] && from_shop[u] == shop) {
                            second_dist[shop] = min(second_dist[shop], temp_dist[v]);
                        }
                    }
                }
                q2.push(v);
            }
        }
    }
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        if (is_shop[i]) {
            cout << (second_dist[i] == INF ? -1 : second_dist[i]) << " ";
        } else {
            cout << (dist[i] == INF ? -1 : dist[i]) << " ";
        }
    }
    
    return 0;
}

算法正确性

关键点证明

1. 多源BFS正确性：所有商店同时作为起点，确保找到全局最近商店
2. 次近商店处理：通过排除自身商店的影响，找到真正的"另一个"商店
3. 边界情况：正确处理孤立城市和无法到达的情况

复杂度分析

• 时间复杂度：$O(n + m)$
• 空间复杂度：$O(n + m)$

样例验证

样例输入分析：

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

• 城市1：到商店2距离1
• 城市2：自身是商店，到商店4距离1
• 城市8：通过1到2，距离2
• 城市6：到商店5距离1
• 城市9：无连接，输出-1

总结

本题的关键在于：

1. 使用多源BFS高效计算最近商店
2. 特殊处理有商店城市的需求（找次近商店）
3. 合理处理边界情况和无法到达的情况

这种"多源BFS + 特殊处理"的模式在解决最近设施类问题时非常有效。