Acwing 2944. 回家的路

题目描述：
2046 年 OI 城的城市轨道交通建设终于全部竣工，由于前期规划周密，建成后的轨道交通网络由 2n 条地铁线路构成，组成了一个 n 纵 n 横的交通网。

如下图所示，这 2n 条线路每条线路都包含 n 个车站，而每个车站都在一组纵横线路的交汇处。

出于建设成本的考虑，并非每个车站都能够进行站内换乘，能够进行站内换乘的地铁站共有 m 个，在下图中，标上方块标记的车站为换乘车站。

已知地铁运行 1 站需要 2 分钟，而站内换乘需要步行 1 分钟。

Serenade 想要知道，在不中途出站的前提下，他从学校回家最快需要多少时间（等车时间忽略不计)。

1.png

输入格式
第一行有两个整数 n,m。

接下去 m 行每行两个整数 x,y，表示第 x 条横向线路与第 y 条纵向线路的交汇站是站内换乘站。

接下去一行是四个整数 x1,y1,x2,y2。表示 Serenade 从学校回家时，在第 x1 条横向线路与第 y1 条纵向线路的交汇站上车，在第 x2 条横向线路与第 y2 条纵向线路的交汇站下车。

输出格式
输出文件只有一行，即 Serenade 在合理选择线路的情况下，回家所需要的时间。

如果 Serenade 无法在不出站换乘的情况下回家，请输出 −1。

数据范围
1≤n≤20000,
1≤m≤105
输入样例：

2 1
1 2
1 1 2 2
1
2
3

输出样例：

5
1

思路：
分层图思想
将横边和纵边分成两个图，若是换乘站就需要将上层图与下层图相连
但这样还不够！不能将所有的点都纳入图中！这样会爆内存！
我们注意到，用到的点其实只有换乘站和起点终点，所以我们只在这些点中建边！
题目描述：

#include
#include 
#include
#include
#include
#include
#include
using namespace std;
typedef pair<int, int> PII;
const int M = 5000005;
const int N=2e5 + 10;
const int T=1e5 + 10;
int e[M],ne[M],w[M],h[N],idx=0;
bool st[N];
int dist[N];
map<PII,int>mp;
void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int cnt=0;

bool cmp1(PII a,PII b)
{
     if(a.first == b.first) return a.second < b.second;
        return a.first < b.first;
}
bool cmp2(PII a,PII b)
{
     if(a.second == b.second) return a.first < b.first;
        return a.second < b.second;
}

int dijkstra(int a,int b)  // 求a号点到b号点的最短路距离
{
    memset(dist, 0x3f, sizeof dist);
    dist[a] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, a});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if(dist[b]==0x3f3f3f3f)
    {
        return -1;
    }
    return dist[b];
}
vector<PII>ve;
int main()
{
    memset(h, -1, sizeof h);
    memset(st, 0, sizeof st);
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        mp[{x,y}]=++cnt;
        int a=mp[{x,y}];
        ve.push_back({x,y});
        add(a,a+T,1);
        add(a+T,a,1);
    }

    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    
    if(!mp.count({x1,y1}))
    {
        mp[{x1,y1}]=++cnt;
    }
    int a=mp[{x1,y1}];
    
    if(!mp.count({x2,y2}))
    {
        mp[{x2,y2}]=++cnt;
    }
    int b=mp[{x2,y2}];
    
    ve.push_back({x1,y1});
    ve.push_back({x2,y2});
    
    add(a,a+T,0);
    add(a+T,a,0);
    add(b,b+T,0);
    add(b+T,b,0);
    
    sort(ve.begin(),ve.end(),cmp1);
    
    for(int i=0;i<ve.size() - 1;i++)
    {
        if(ve[i].first==ve[i+1].first)
        {        
            int a=mp[{ve[i].first,ve[i].second}];
            int b=mp[{ve[i+1].first,ve[i+1].second}];
            int dis=abs((ve[i+1].second-ve[i].second))*2;
            add(a,b,dis);
            add(b,a,dis);
        }
    }
    
    sort(ve.begin(),ve.end(),cmp2);
    
    for(int i=0;i<ve.size() - 1;i++)
    {
        if(ve[i].second==ve[i+1].second)
        {        
            int a=mp[{ve[i].first,ve[i].second}];
            int b=mp[{ve[i+1].first,ve[i+1].second}];
            int dis=abs((ve[i+1].first-ve[i].first))*2;
            add(a+T,b+T,dis);
            add(b+T,a+T,dis);
        }
    }
    
    cout<<dijkstra(a,b);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138