AtCoder Beginner Contest 299E – Nearest Black Vertex

E - Nearest Black Vertex 题目链接

题意

给你一个$n$点$m$边的无向图，每个点需要染成黑色或白色，有$k$个限制$(p_i, d_i)$为距离$p_i$点最近的黑点距离为$d_i$，求是否存在这样的图，若有多种方案输出任意一种即可。
数据范围：$2\le n\le 2000,\ n - 1\le m\le \min\lbrace \frac{n\times (n−1)}{2},2000\rbrace, 0\le k\le n$

思路

注释都写在代码上了，这里想写的原因是，如果边权为1的话，可以对每个点进行一次bfs来获得其他点到该点的最短距离，所以只需要对每个点跑一次O(m)的bfs即可，时间复杂度是O(nm)，这个题注意m的范围最多2000，所以是可以的，一开始我忽略了这一点。

代码

struct node {
    int to, next;
}edge[N << 1];
int head[N], dis[N][N], need[N];
PII query[N];
inline void add(int x, int to) {
    edge[++cnt].to = to;
    edge[cnt].next = head[x];
    head[x] = cnt;
}
inline void bfs(int st) {
    queue<PII> q;
    q.emplace(st, 0);// q存pair(a,b)，也就是从当前st点开始bfs到a点的距离为b
    memset(vis, 0, sizeof(vis));
    vis[st] = 1;
    while (!q.empty()) {
        auto [x, d] = q.front(); q.pop();
        for (int i = head[x]; i; i = edge[i].next) {
            int y = edge[i].to;
            if (vis[y]) continue;// 入队就不再入队了
            vis[y] = 1;
            dis[st][y] = d + 1;// dis[st][y] = dis[st][x] + 1，st到y的距离等于st到x的距离+1
            q.emplace(y, d + 1);
        }
    }
}

inline void Case_Test() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v); add(v, u);
    }
    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> query[i].first >> query[i].second;
    }// 先存一下 后面要验证的
    for (int i = 1; i <= n; i++) {
        bfs(i);
    }// 对于每一个点跑一次全图，获得点i到其他点的最短路，每次时间复杂度是O(m),一共n次
    for (int i = 1; i <= n; i++) {
        bool ok = true;// 每个点都涂黑试一试，用k次的限制去判断可以不可以，如果可以就涂黑
        for (int j = 1; j <= k; j++) {
            auto [x, d] = query[j];// 距离x最近的黑点为d
            if (dis[x][i] < d) ok = false;// 如果x到当前尝试图黑的点i距离小于限制的d，那么就不可以
        }
        ans[i] = ok;// 不可以就填0，可以ok还是1
        if (ok) {// 如果可以
            for (int j = 1; j <= k; j++) {
                auto [x, d] = query[j];
                if (dis[x][i] == d) need[j] = 1;// 那么就去看是否等于，有等于代表第j个限制满足了
                // 因为不仅仅判断是否小于d，还需要判断是否有等于的（题目要求等于）
            }
        }
    }
    for (int i = 1; i <= k; i++) {
        if (!need[i]) {// 如果有一个不满足，那么就不可以
            No;
            return;
        }
    }
    Yes;
    for (int i = 1; i <= n; i++) {
        cout << ans[i];
    }// 否则输出ans[]
}