P3831 [SHOI2012]回家的路

思路

很简单 分层图 + \(SPFA\)

坑点

我提交了\(10+\)次 全部\(90pts\)

希望各位大佬不会跟我犯一样的错误

空间大小不要开错了

不然会\(WA\) 而不是\(RE\) 半天差不出来错的那种（第二个点一直错）

点 开 \(3e5 + 10\)

边开 \(3e6 + 10\)

这题没有卡\(SPFA\)

不用堆优化 （374ms）在题解中算挺快的

不用开\(long long\)

\(Code\)

#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template<typename T>
inline T Read(T Type)
{
    T x = 0,f = 1;
    char a = getchar();
    while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
    while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
    return x * f;
}
const int MAXN = 3e5 + 10,MAXM = 3e6 + 10;
struct node
{
    int x,y,num;
}sta[MAXN];
bool cmp1(node a,node b)
{
    if(a.x < b.x) return 1;
    if(a.x == b.x) return (a.y < b.y?1:0);
    return 0;
}
bool cmp2(node a,node b)
{
    if(a.y < b.y) return 1;
    if(a.y == b.y) return (a.x < b.x?1:0);
    return 0;
}
inline int cost(int a,int b) {return (a - b > 0?a - b:b - a) * 2;}
struct EDGE
{
    int u,v,w,next;
}edge[MAXM];
int n,m,cnt,head[MAXN];
inline void addedge(int u,int v,int w)
{
    edge[++cnt].u = u;
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt;
}
inline void add(int u,int v,int w) {addedge(u,v,w),addedge(v,u,w);}
inline void buildgraph()
{
    sort(sta + 1,sta + 3 + m,cmp1);
    for(reg i = 2;i <= m + 2;i++)
        if(sta[i].x == sta[i - 1].x)
            add(sta[i].num,sta[i - 1].num,cost(sta[i - 1].y,sta[i].y));
    sort(sta + 1,sta + 3 + m,cmp2);
    for(reg i = 2;i <= m + 2;i++)
        if(sta[i].y == sta[i - 1].y)
            add(sta[i].num + m + 2,sta[i - 1].num + m + 2,cost(sta[i - 1].x,sta[i].x));
    for(reg i = 1;i <= m + 2;i++)
        add(sta[i].num,sta[i].num + m + 2,(sta[i].num > m?0:1));
}
bool vis[MAXN];
int d[MAXN];
inline int dijkstra(int s,int t)
{
    queue<int> q;
    q.push(s);
    vis[s] = 1;
    memset(d,0x7f7f7f,sizeof(d));
    d[s] = 0;
    while(!q.empty())
    {
        int tp = q.front();q.pop();
        vis[tp] = 0;
        for(reg e = head[tp];e;e = edge[e].next)
        {
            int v = edge[e].v,w = edge[e].w;
            if(d[tp] + w < d[v])
            {
                d[v] = d[tp] + w;
                if(!vis[v]) q.push(v);
                vis[v] = 1;
            }
        }
    }
    return (d[t] < 0x7f7f7f?d[t]:-1);
}
int main()
{
    n = Read(1),m = Read(1);
    for(reg i = 1;i <= m + 2;i++)
        sta[i].x = Read(1),sta[i].y = Read(1),sta[i].num = i;
    buildgraph();
    int ans = dijkstra(m + 1,m + 2);
    printf("%d",ans);
    return 0;
}