题解：酒店位置候选城市判定（最短路径约束验证）

核心结论：酒店候选城市需满足「对所有有记录的 (d_i \neq -1)，该城市到 (i) 的最短路径长度恰好等于 (d_i)」，通过筛选候选集+多源BFS验证，高效求解。

一、核心思路

1. 问题本质：找城市 (x)，使得对所有 (i)（(d_i \neq -1)），(\text{dist}(x, i) = d_i)（(\text{dist}) 表示最短路径长度）。
2. 关键观察：
   • 若 (d_i \neq -1)，则候选城市 (x) 必须满足 (\text{dist}(x, i) = d_i)，即 (x) 一定在「距离 (i) 为 (d_i) 的城市集合」中。
   • 所有有记录的 (d_i) 对应的集合的交集，就是候选城市的候选集（极大缩小验证范围）。
3. 验证方法：对候选集中的每个城市，单独计算它到所有有记录 (d_i) 的城市的最短路径，判断是否完全匹配。

二、具体步骤

1. 筛选候选集

• 收集所有非 -1 的 (d_i)，记为约束列表 (S = {(i, d_i) | d_i \neq -1})。
• 若 (S) 为空：所有城市都是候选（输出 1~n）。
• 若 (S) 非空：
  • 取 (S) 中第一个元素 ((u, d_u))，计算所有城市到 (u) 的最短路径，筛选出距离为 (d_u) 的城市集合 (candidates)。
  • 对 (S) 中剩余的每个 ((v, d_v))，计算所有城市到 (v) 的最短路径，将 (candidates) 与「距离 (v) 为 (d_v) 的集合」取交集，更新 (candidates)。
  • 若过程中 (candidates) 为空，直接输出 0。

2. 验证候选城市

• 对 (candidates) 中的每个城市 (x)：
  • 计算 (x) 到所有 (S) 中城市 (i) 的最短路径长度。
  • 若所有长度都等于对应的 (d_i)，则 (x) 是合法候选。
• 收集所有合法候选，排序后输出。

3. 优化技巧

• 多源BFS替代多次单源BFS：计算多个城市到所有节点的最短路径时，可将这些城市作为起点同时入队，一次BFS完成（适用于筛选候选集时的多轮距离计算）。
• 候选集早剪枝：每轮筛选后立即缩小候选集，避免后续无效计算。

三、代码实现

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

const int MAXN = 5e4 + 5;
const int INF = 1e9;

vector<int> adj[MAXN];  // 邻接表
vector<pair<int, int>> constraints;  // 非-1的(d_i, i)，注意顺序：(距离, 城市)
vector<int> candidates;
int dist[MAXN];  // 存储单源/多源BFS的距离

// 单源BFS：计算start到所有节点的最短距离
void bfs_single(int start, int n) {
    fill(dist, dist + n + 1, INF);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == INF) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

// 多源BFS：计算多个start节点到所有节点的最短距离
void bfs_multi(const vector<int>& starts, int n) {
    fill(dist, dist + n + 1, INF);
    queue<int> q;
    for (int s : starts) {
        dist[s] = 0;
        q.push(s);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == INF) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> d(n + 1);  // d[1..n]
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
        if (d[i] != -1) {
            constraints.emplace_back(d[i], i);
        }
    }

    // 步骤1：筛选候选集
    if (constraints.empty()) {
        // 无约束，所有城市都是候选
        cout << n << '\n';
        for (int i = 1; i <= n; ++i) {
            cout << i << " ";
        }
        cout << '\n';
        return 0;
    }

    // 初始候选集：满足第一个约束的城市
    auto [d0, u0] = constraints[0];
    bfs_single(u0, n);
    for (int x = 1; x <= n; ++x) {
        if (dist[x] == d0) {
            candidates.push_back(x);
        }
    }

    // 用剩余约束筛选候选集
    for (int k = 1; k < constraints.size() && !candidates.empty(); ++k) {
        auto [dk, uk] = constraints[k];
        bfs_single(uk, n);
        vector<int> new_candidates;
        for (int x : candidates) {
            if (dist[x] == dk) {
                new_candidates.push_back(x);
            }
        }
        candidates.swap(new_candidates);
    }

    // 步骤2：验证候选集（确保候选x到所有约束城市的距离都符合）
    vector<int> ans;
    for (int x : candidates) {
        bfs_single(x, n);
        bool valid = true;
        for (auto [di, i] : constraints) {
            if (dist[i] != di) {
                valid = false;
                break;
            }
        }
        if (valid) {
            ans.push_back(x);
        }
    }

    // 输出结果
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for (int x : ans) {
        cout << x << " ";
    }
    if (!ans.empty()) {
        cout << '\n';
    }

    return 0;
}

四、复杂度分析

• 时间复杂度：(O((n + m) \times K))，其中 (K) 是约束数量（非 -1 的 (d_i) 个数）。
  • 每次BFS复杂度为 (O(n + m))，筛选候选集最多需 (K) 次BFS，验证候选集需 (O(C \times (n + m)))（(C) 是候选集大小，通常很小）。
  • 整体复杂度适配 (n \leq 5e4)、(m \leq 1e5) 的数据规模。
• 空间复杂度：(O(n + m))，用于存储邻接表和距离数组。

五、关键注意点

1. 距离合法性：题目中 (d_i < n)，而树的最大最短路径（直径）不超过 (n-1)，图的最短路径更短，因此无需额外判断 (d_i) 的有效性。
2. 候选集筛选顺序：优先用约束数量少的筛选，或任意顺序均可，核心是早剪枝。
3. 多源BFS优化：若约束数量多，可将所有约束城市作为起点做一次多源BFS，再根据距离筛选候选集（需调整筛选逻辑），进一步减少BFS次数。

六、样例解析

样例1

• 约束：(d_1=2)，(d_7=3)。
• 第一步：筛选距离1为2的城市，得到 {4,5,6}。
• 第二步：筛选距离7为3的城市，{4,5,6} 中距离7为3的是 {4,6}。
• 验证：4到1的距离为2、到7的距离为3；6到1的距离为2、到7的距离为3，均合法，输出 {4,6}。

样例3

• 约束：(d_1=1)，(d_4=1)。
• 筛选距离1为1的城市：{2}；距离4为1的城市：{3}。
• 交集为空，直接输出0。

该解法通过「筛选+验证」两步走，高效缩小候选范围，避免暴力枚举所有城市，是处理大规模图问题的常用思路。