比赛 2025暑期集训第5场图论专场 评测结果 AAAAAAAAAAA
题目名称 激光 最终得分 100
用户昵称 健康铀 运行时间 1.118 s
代码语言 C++ 内存使用 14.99 MiB
提交时间 2025-07-09 10:08:34
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
    freopen("lasers.in", "r", stdin);
    freopen("lasers.out", "w", stdout);

    int N;
    LL xL, yL, xB, yB;
    cin >> N >> xL >> yL >> xB >> yB;

    vector<tuple<LL, LL>> pts;
    pts.push_back({xL, yL});
    pts.push_back({xB, yB});
    for (int i = 0; i < N; i++) {
        LL x, y;
        cin >> x >> y;
        pts.push_back({x, y});
    }

    int tot = pts.size();
    map<LL, vector<pair<LL, int>>> mx, my;

    for (int i = 0; i < tot; i++) {
        LL x = get<0>(pts[i]);
        LL y = get<1>(pts[i]);
        mx[x].push_back({y, i});
        my[y].push_back({x, i});
    }

    vector<vector<vector<tuple<int, int, int>>>> gr(tot, vector<vector<tuple<int, int, int>>>(2));

    for (int i = 0; i < tot; i++) {
        gr[i][0].push_back({i, 1, 1});
        gr[i][1].push_back({i, 0, 1});
    }

    for (auto &p : mx) {
        auto &vec = p.second;
        sort(vec.begin(), vec.end());
        for (int j = 0; j < (int)vec.size() - 1; j++) {
            int u = vec[j].second;
            int v = vec[j+1].second;
            gr[u][0].push_back({v, 0, 0});
            gr[v][0].push_back({u, 0, 0});
        }
    }

    for (auto &p : my) {
        auto &vec = p.second;
        sort(vec.begin(), vec.end());
        for (int j = 0; j < (int)vec.size() - 1; j++) {
            int u = vec[j].second;
            int v = vec[j+1].second;
            gr[u][1].push_back({v, 1, 0});
            gr[v][1].push_back({u, 1, 0});
        }
    }

    const int INF = 0x3f3f3f3f;
    vector<vector<int>> dist(tot, vector<int>(2, INF));
    deque<pair<int, int>> dq;

    dist[0][0] = 0;
    dist[0][1] = 0;
    dq.push_back({0, 0});
    dq.push_back({0, 1});

    while (!dq.empty()) {
        int u = dq.front().first;
        int d = dq.front().second;
        dq.pop_front();
        for (auto &edge : gr[u][d]) {
            int v = get<0>(edge);
            int d2 = get<1>(edge);
            int w = get<2>(edge);
            if (dist[u][d] + w < dist[v][d2]) {
                dist[v][d2] = dist[u][d] + w;
                if (w == 0) {
                    dq.push_front({v, d2});
                } else {
                    dq.push_back({v, d2});
                }
            }
        }
    }

    int ans = min(dist[1][0], dist[1][1]);
    if (ans >= INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}