传送门
题意:在n x n(1e9)的坐标系内,开始位于起点(x0, y0), 要去(x1, y1), 有m(1e5)个跳转点当x或y坐标相同时可以直接到达,问最少步数;
到达终点可以从起点直接走到或跳转点走到 将m个点离散化,每个点的x坐标和y坐标与点连边,每个跳转点再与终点连边,计算最短路即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int>pii;
const int maxn = 1e6+5;
int cnt = 0;
int head[maxn], to[maxn], nxt[maxn], val[maxn];
ll d[maxn];
struct cmp
{bool operator()(pii a, pii b){return a.first > b.first;}
};void add_edge(int x, int y, int z)
{to[++cnt] = y;nxt[cnt] = head[x];head[x] = cnt;val[cnt] = z;to[++cnt] = x;nxt[cnt] = head[y];head[y] = cnt;val[cnt] = z;
}
void dijkstra(int x)
{memset(d, 0x3f, sizeof(d));d[x] = 0;priority_queue<pii, vector<pii>, cmp>q;q.emplace(0, x);while(!q.empty()){auto t = q.top();q.pop();if(d[t.second] < t.first)continue;for(int i = head[t.second]; i; i = nxt[i]){int j = to[i];if (d[j] > d[t.second] + val[i]){d[j] = d[t.second] + val[i];q.emplace(d[j], j);}}}
}
int main()
{int n,m;vector<pii>a;vector<int>xx, yy;while(cin >>n >>m){int x0,y0,x1,y1;cin >> x0 >> y0 >> x1 >> y1;a.emplace_back(x0, y0);a.emplace_back(x1, y1); xx.emplace_back(x0), xx.emplace_back(x1);yy.emplace_back(y0), yy.emplace_back(y1);for(int i = 0; i < m; ++i){int x, y;cin >> x >> y;a.emplace_back(x, y);xx.emplace_back(x), yy.emplace_back(y);}sort(xx.begin(), xx.end());xx.erase(unique(xx.begin(), xx.end()), xx.end());for(int i = 1; i < xx.size(); ++i){add_edge(i + a.size() - 1, i + a.size(), xx[i] - xx[i - 1]);// cout << "**" << i + a.size() - 1 << " " << i + a.size() << " " << xx[i] - xx[i - 1] << endl;}sort(yy.begin(), yy.end());yy.erase(unique(yy.begin(), yy.end()), yy.end());for (int i = 1; i < yy.size(); ++i) {add_edge(i + a.size() + xx.size() - 1, i + a.size() + xx.size(), yy[i] - yy[i - 1]);// cout << "**" << i + a.size() + xx.size() - 1 << " " << i + a.size() + xx.size() << " " << yy[i] - yy[i - 1] << endl;}auto get_x_coord = [&](int x){return lower_bound(xx.begin(), xx.end(), x) - xx.begin() + a.size();};auto get_y_coord = [&](int x) { return lower_bound(yy.begin(), yy.end(), x) - yy.begin() + a.size() + xx.size(); };for(int i = 0; i < a.size(); ++i){if(i == 1)continue;add_edge(i, get_x_coord(a[i].first), 0);add_edge(i, get_y_coord(a[i].second), 0);// cout << i << " " << get_x_coord(a[i].first) << " " << 0 << endl;// cout << i << " " << get_y_coord(a[i].second) << " " << 0 << endl;// cout << i << " " << 1 << " " << abs(a[i].first - a[1].first) + abs(a[i].second - a[1].second) << endl;add_edge(i, 1, abs(a[i].first - a[1].first) + abs(a[i].second - a[1].second));}dijkstra(0);cout << d[1] << endl;}
}