lessons/参考实现/05-最短路与类最短路/AtCoder-agc056_c.cpp

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

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

    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 0; i < n; ++i) {
        graph[i].push_back({i + 1, 1});
        graph[i + 1].push_back({i, 1});
    }
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        --l;
        graph[l].push_back({r, 0});
        graph[r].push_back({l, 0});
    }

    const int inf = numeric_limits<int>::max() / 4;
    vector<int> distance(n + 1, inf);
    deque<int> queue;
    distance[0] = 0;
    queue.push_back(0);
    while (!queue.empty()) {
        int u = queue.front();
        queue.pop_front();
        for (auto [v, weight] : graph[u]) {
            if (distance[v] <= distance[u] + weight) continue;
            distance[v] = distance[u] + weight;
            if (weight == 0) queue.push_front(v);
            else queue.push_back(v);
        }
    }
    string answer;
    answer.reserve(n);
    for (int i = 1; i <= n; ++i) {
        answer.push_back(distance[i] > distance[i - 1] ? '0' : '1');
    }
    cout << answer << '\n';
    return 0;
}