比赛 |
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;
}