[SHOI2012]回家的路

C++(g++ 7.5.0) 解法, 执行用时: 164ms, 内存消耗: 20940K, 提交时间: 2022-09-25 01:14:56

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

const int N = 200010, M = 1000010, INF = 0x3f3f3f3f;

struct State {
    int d, u;
    bool operator< (const State& other) const {
        return d > other.d;
    }
};
int e[M], ne[M], h[N], w[M], dis[N], idx;
int n, m;
bool vis[N];
int x[N], y[N];
vector<int> r[N], c[N];

void insert(int u, int v, int d) {
    e[idx] = v, w[idx] = d, ne[idx] = h[u], h[u] = idx++;
    e[idx] = u, w[idx] = d, ne[idx] = h[v], h[v] = idx++;
}

void dijkstra() {
    priority_queue<State> heap;
    memset(dis, 0x3f, sizeof dis);
    dis[0] = 0, heap.push({0, 0});
    dis[m + 2] = 0, heap.push({0, m + 2});
    while (heap.size()) {
        auto [d, u] = heap.top();
        heap.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (dis[j] > d + w[i]) {
                dis[j] = d + w[i];
                heap.push({dis[j], j});
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> x[i] >> y[i];
    cin >> x[0] >> y[0] >> x[m + 1] >> y[m + 1];
    for (int i = 0; i <= m + 1; i++) {
        r[x[i]].push_back(i);
        c[y[i]].push_back(i);
        insert(i, i + m + 2, 1);
    }
    for (int i = 1; i <= 20000; i++) {
        sort(r[i].begin(), r[i].end(), [](int a, int b) { return y[a] < y[b]; });
        if (r[i].size() > 1) 
            for (int j = 0; j < r[i].size() - 1; j++)
                insert(r[i][j], r[i][j + 1], 2 * (y[r[i][j + 1]] - y[r[i][j]]));
        sort(c[i].begin(), c[i].end(), [](int a, int b) { return x[a] < x[b]; });
        if (c[i].size() > 1) 
            for (int j = 0; j < c[i].size() - 1; j++)
                insert(c[i][j] + m + 2, c[i][j + 1] + m + 2, 2 * (x[c[i][j + 1]] - x[c[i][j]]));
    }
    dijkstra();
    cout << min(dis[m + 1], dis[2 * m + 3]);
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 238ms, 内存消耗: 26028K, 提交时间: 2022-10-20 11:58:50

#include<bits/stdc++.h>
using namespace std;

#define pos(x,y) (x-1)*n+y
typedef pair<int,int> pa;
const int MAXN=2e5+5;
const int MAXM=1e5+5;
const int MAXX=2e4+5;
struct node{int x,y;}a[MAXM];
vector<pa>G[MAXN];
vector<int>X[MAXX],Y[MAXX];
int dis[MAXN];
bool vis[MAXN];
int s,t;
void dijkstra()
{
    priority_queue< pa,vector<pa>,greater<pa> >q;
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0,q.push({dis[s],s});
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(auto [y,z]:G[x]) if(dis[y]>dis[x]+z) dis[y]=dis[x]+z,q.push({dis[y],y});
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    s=m*2+1,t=m*2+2;
    int x,y,cnt=0;
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d",&x,&y),a[++cnt]={x,y};
        for(auto p:X[x]) G[cnt].push_back({p,abs(y-a[p].y)*2}),G[p].push_back({cnt,abs(y-a[p].y)*2});
        for(auto p:Y[y]) G[cnt+m].push_back({p+m,abs(x-a[p].x)*2}),G[p+m].push_back({cnt+m,abs(x-a[p].x)*2});
        G[cnt].push_back({cnt+m,1}),G[cnt+m].push_back({cnt,1});
        X[x].push_back(cnt),Y[y].push_back(cnt);
    }
    cin>>x>>y;
    for(auto p:X[x]) G[s].push_back({p,abs(y-a[p].y)*2});
    for(auto p:Y[y]) G[s].push_back({p+m,abs(x-a[p].x)*2});
    cin>>x>>y;
    for(auto p:X[x]) G[p].push_back({t,abs(y-a[p].y)*2});
    for(auto p:Y[y]) G[p+m].push_back({t,abs(x-a[p].x)*2});
    dijkstra();
    printf("%d",dis[t]==0x3f3f3f3f?-1:dis[t]);
    return 0;
}

详情