站外题求助

学术版

Register_int @ 2022-07-14 20:01:11

题目大意：给定平面上的 n 个点，定义 (x1,y1) 到 (x2,y2) 的费用为 \min(|x1-x2|,|y1-y2|)，求从 1 号点走到 n 号点的最小费用。2\le n\le2\times10^5。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;
const int MAXM = 4e5 + 10;

struct edge {
    ll v, w, nxt;
} e[MAXM << 2];

int head[MAXN], tot;

inline 
void add(int u, int v, ll w) {
    e[++tot] = { v, w, head[u] }, head[u] = tot;
}

struct node {
    ll u, dis;
    bool operator < (const node &rhs) const { return dis > rhs.dis; }
};

priority_queue<node> q;

bool vis[MAXN];

ll dis[MAXN];

inline 
ll dijkstra(int s, int t) {
    memset(dis, 0x3f, sizeof dis);
    q.push({ s, 0 }), dis[s] = 0, vis[s] = 1;
    while (!q.empty()) {
        int u = q.top().u; q.pop();
        for (int i = head[u], v; i; i = e[i].nxt) {
            v = e[i].v;
            if (!vis[v] && dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w, q.push({ v, dis[v] });
            }
        }
    }
    return dis[t];
}

struct pos {
    int id, x, y;
} a[MAXN];

bool cmpx(pos p, pos q) {
    return p.x == q.x ? p.y < q.y : p.x < q.x;
}

bool cmpy(pos p, pos q) {
    return p.y == q.y ? p.x < q.x : p.y < q.y;
}

int n;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].x, &a[i].y), a[i].id = i;
    sort(a + 1, a + n + 1, cmpx);
    for (int i = 1, w; i < n; i++) {
        w = min(abs(a[i].x - a[i + 1].x), abs(a[i].y - a[i + 1].y));
        add(a[i].id, a[i + 1].id, w);
    }
    sort(a + 1, a + n + 1, cmpy);
    for (int i = 1, w; i < n; i++) {
        w = min(abs(a[i].x - a[i + 1].x), abs(a[i].y - a[i + 1].y));
        add(a[i].id, a[i + 1].id, w);
    }
    printf("%lld", dijkstra(1, n));
}

样例都没过……
输入样例：

输出样例：

by Ctrl_Z @ 2022-07-14 20:28:46


#include<bits/stdc++.h>
using namespace std;
const int maxn=800099;
int m, head[maxn], tot, dis[maxn],vis[maxn];

struct edge{
    int to, next, w;
}g[maxn];
struct node{
    int i,dis;
    bool operator < (const node tmp)const{
        return tmp.dis<dis;
    }
}e[maxn];

struct Node{
    int x,y,id;
}a[maxn];

bool cmp_x(Node x,Node y) {return x.x<y.x;}  
bool cmp_y(Node x,Node y) {return x.y<y.y;}  

void add(int a, int b, int w) {
    g[++tot].to = b;
    g[tot].w = w;
    g[tot].next = head[a];
    head[a] = tot;
}

priority_queue<node>q;

int main() {
    scanf("%d",&m);

    memset(dis, 0x3f, sizeof(dis));
    dis[1]=0;

    for(int i=1;i<=m;i++){
        cin>>a[i].x>>a[i].y;  
        a[i].id=i; 
    }

    sort(a+1,a+m+1,cmp_x);  
    for(int i=1;i<m;i++){
        if(a[i+1].x-a[i].x<=abs(a[i+1].y-a[i].y))add(a[i].id,a[i+1].id,a[i+1].x-a[i].x),add(a[i+1].id,a[i].id,a[i+1].x-a[i].x);
    }
    sort(a+1,a+m+1,cmp_y);  
    for(int i=1;i<m;i++) {
        if(a[i+1].y-a[i].y<=abs(a[i+1].x-a[i].x))add(a[i].id,a[i+1].id,a[i+1].y-a[i].y),add(a[i+1].id,a[i].id,a[i+1].y-a[i].y);
    }

    q.push((node){1,0});

    while(!q.empty()){
        node temp=q.top();
        q.pop();
        //cout<<temp.i<<" "<<temp.dis<<endl;
        int now=temp.i;
        for(int i=head[now];i;i=g[i].next){
            int next=g[i].to;
            if(dis[next]>dis[now]+g[i].w){
                dis[next]=dis[now]+g[i].w;
                q.push((node){next,dis[next]});
            }
        }
    }

    cout<<dis[m];
    return 0;
}

by bmqt @ 2022-07-14 20:32:03

这题来源？

by bmqt @ 2022-07-14 20:32:20

什么题