LYDSY 4152

题目大意

暂无

题目解法

暂无

RTFC

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 200010;
inline void readInt(int &x)
{
    int ch = x = 0;
    while (!isdigit(ch = getchar()))
        ;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
}
int head[maxn], to[maxn << 2], nxt[maxn << 2], len[maxn << 2], ecnt, n;
inline void addEdge(int f, int t, int l)
{
    ecnt++;
    nxt[ecnt] = head[f];
    head[f] = ecnt;
    to[ecnt] = t;
    len[ecnt] = l;
}
struct P
{
    int id, x, y;
} ps[maxn];
bool cmpx(const P &lhs, const P &rhs) { return lhs.x < rhs.x; }
bool cmpy(const P &lhs, const P &rhs) { return lhs.y < rhs.y; }
int pathlen[maxn];
struct heapnode
{
    int id, dis;
    heapnode(int x, int y) : id(x), dis(y) {}
    bool operator<(const heapnode &rhs) const { return dis > rhs.dis; }
};
int main()
{
    readInt(n);
    for (int i = 0; i < n; i++) ps[i].id = i + 1, readInt(ps[i].x), readInt(ps[i].y);
    sort(ps, ps + n, cmpx);
    for (int i = 0; i < n - 1; i++)
        addEdge(ps[i].id, ps[i + 1].id, ps[i + 1].x - ps[i].x),
            addEdge(ps[i + 1].id, ps[i].id, ps[i + 1].x - ps[i].x);
    sort(ps, ps + n, cmpy);
    for (int i = 0; i < n - 1; i++)
        addEdge(ps[i].id, ps[i + 1].id, ps[i + 1].y - ps[i].y),
            addEdge(ps[i + 1].id, ps[i].id, ps[i + 1].y - ps[i].y);
    memset(pathlen, 0x3f3f3f3f, sizeof(pathlen));
    pathlen[1] = 0;
    priority_queue<heapnode> Q;
    Q.push(heapnode(1, 0));
    while (!Q.empty())
    {
        heapnode x = Q.top();
        Q.pop();
        if (x.dis > pathlen[x.id]) continue;
        for (int cur = head[x.id]; cur; cur = nxt[cur])
            if (pathlen[to[cur]] > pathlen[x.id] + len[cur])
            {
                pathlen[to[cur]] = pathlen[x.id] + len[cur];
                Q.push(heapnode(to[cur], pathlen[to[cur]]));
            }
    }
    printf("%d", pathlen[n]);
    return 0;
}