洛谷 P3831 - 做题记录

发表于 分类于 Disqus： 本文字数： 1.2k 阅读时长 ≈ 4 分钟
洛谷 P3831 - 做题记录

原题链接

  • 洛谷 P3831 [SHOI2012] 回家的路

题目信息

使用的算法

  • 图论
  • 最短路

难度

  • 洛谷：提高 +/ 省选 -
  • 本人：0.7

简化题意

给出一个 $n \times n$ 的地图，在这个地图上有 $m$ 个点可以使横向与纵向的直线（线段）相连， 经过一条线段所花费的时间为 $2$， 方向改变所花费的时间为 $1$，询问从某一点 $(x_{from}, y_{from})$ 出发，到 $(x_{to}, y_{to})$ 的距离最短是多少（无法到达则为 $-1$）。

思想方法

  • 由到达的最短时间我们可以很容易想到使用最短路进行求解
  • 可以将每个交汇点当作图中的一个节点进行存储
  • 每个节点之间的距离保存为他们之间的线段数量的两倍

代码实现

保存交汇节点

1
2
3
4
5
6
7
8
9
10
11
class Station {
public:
  unsigned int id, x, y;

  Station(const unsigned int &id, const unsigned int &x,
          const unsigned int &y) {
    this->id = id;
    this->x = x;
    this->y = y;
  }
};

存边

1
2
3
4
5
6
7
8
9
10
11
class Edge {
public:
  unsigned int from, to, len;

  Edge(const unsigned int &from, const unsigned int &to,
       const unsigned int &len) {
    this->from = from;
    this->to = to;
    this->len = len;
  }
};

存图

1
2
3
unsigned int n, m;
vector<Station> stations;
vector<Edge> graph[MAX_M];

首先判断答案是否为 $-1$

  • 当起点所在的坐标 $(x_{from}, y_{from})$ 时， 如没有坐标为 $(x_{from}, y)$ 或 $(x, y_{from})$ 的交汇点时无法到达终点， 因为无法通过交汇点到达目标（除非目标的任一坐标与起点相同），目标同理
  • 即可想到使用 set 存储交汇点的 $(x, y)$ 坐标 
1
2
3
4
5
6
7
set<unsigned int> coordinateX;
set<unsigned int> coordinateY;
if ((!coordinateX.count(xFrom) and !coordinateY.count(yFrom)) or
    (!coordinateX.count(xTo) and !coordinateY.count(yTo))) {
  cout << -1 << endl;
  exit(0);
}

接着进行建图

  • 先将起点与目标当作交汇点存入 stations
  • 遍历 stations，将 $x$ 坐标相同的节点互相连接起来（无向边）, $y$ 坐标同理
  • 为了更好的遍历，我们需要先对 stations 进行排序 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline bool compX(const Station &x, const Station &y) { return x.x < y.x; }
inline bool compY(const Station &x, const Station &y) { return x.y < y.y; }

sort(stations.begin(), stations.end(), compX);
for (unsigned int i = 0; i < stations.size() - 1; ++i) {
  for (unsigned int j = i + 1;
        (stations[j].x == stations[i].x) and (j < stations.size()); ++j) {
    addEdge(stations[i].id, stations[j].id,
            abs(stations[i].y - stations[j].y));
  }
}

sort(stations.begin(), stations.end(), compY);
for (unsigned int i = 0; i < stations.size() - 1; ++i) {
  for (unsigned int j = i + 1;
        (stations[j].y == stations[i].y) and (j < stations.size()); ++j) {
    addEdge(stations[i].id, stations[j].id,
            sabs(stations[i].x - stations[j].x));
  }
}

跑 Dijkstra

  • 为了加速，我们使用堆优化的 Dijkstra
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
inline bool operator<(const Edge &x, const Edge &y) { return x.len > y.len; }

array<unsigned int, MAX_M> dis;
bitset<MAX_M> vis;

fill(dis.begin(), dis.end(), INT32_MAX);

priority_queue<Edge> heap;
heap.push(Edge(0, 0, 0));
dis[0] = 0;

while (heap.size()) {
  unsigned int now = heap.top().from;
  heap.pop();

  if (vis[now]) {
    continue;
  }
  vis[now] = true;

  for (auto i : graph[now]) {
    if (dis[i.to] > dis[now] + i.len) {
      dis[i.to] = dis[now] + i.len;
      heap.push(Edge(i.to, 0, dis[i.to]));
    }
  }
}

最后，输出答案

1
cout << dis[目标] << endl;

完整代码

  • 由于数据点没有 $-1$ 的情况，所以省略判断 $-1$
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
139
140
141
142
143
144
// Copyright (c) 2021 bmyjacks
// LastModified: 2021/7/1 下午7:24
// License: GPLv3
// Author: bmyjacks

#include <algorithm>
#include <array>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

const unsigned int MAX_M = 1e5 + 2;

class Station {
public:
  unsigned int id, x, y;
  Station(const unsigned int &id, const unsigned int &x,
          const unsigned int &y) {
    this->id = id;
    this->x = x;
    this->y = y;
  }
};
class Edge {
public:
  unsigned int from, to;
  unsigned int len;
  Edge(const unsigned int &from, const unsigned int &to,
       const unsigned int &len) {
    this->from = from;
    this->to = to;
    this->len = len;
  }
};

unsigned int n, m;
vector<Station> stations;
vector<Edge> graph[MAX_M];
array<unsigned int, MAX_M> dis;
bitset<MAX_M> vis;

inline void addEdge(const unsigned int &from, const unsigned int &to,
                    const unsigned int &len) {
  graph[from].emplace_back(Edge(from, to, len));
  graph[to].emplace_back(Edge(to, from, len));
}

inline bool operator<(const Edge &x, const Edge &y) { return x.len > y.len; }
inline bool compX(const Station &x, const Station &y) { return x.x < y.x; }
inline bool compY(const Station &x, const Station &y) { return x.y < y.y; }
inline unsigned int stationsDistance(const unsigned int &x,
                                     const unsigned int &y) {
  return x > y ? ((x - y) * 2 + 1) : ((y - x) * 2 + 1);
}

inline unsigned int read() {
  unsigned int x = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - 48;
    ch = getchar();
  }
  return x;
}

void write(const unsigned int x) {
  if (x > 9) {
    write(x / 10);
  }
  putchar(x % 10 + 48);
}

int main() {
  n = read();
  m = read();

  for (unsigned int i = 1, x, y; i <= m; ++i) {
    x = read();
    y = read();
    stations.push_back(Station(i, x, y));
  }

  long long xFrom, yFrom, xTo, yTo;
  xFrom = read();
  yFrom = read();
  xTo = read();
  yTo = read();
  stations.emplace_back(Station(0, xFrom, yFrom));
  stations.emplace_back(Station(m + 1, xTo, yTo));

  sort(stations.begin(), stations.end(), compX);
  for (unsigned int i = 0; i < stations.size() - 1; ++i) {
    for (unsigned int j = i + 1; stations[j].x == stations[i].x; ++j) {
      addEdge(stations[i].id, stations[j].id,
              stationsDistance(stations[i].y, stations[j].y));
    }
  }

  sort(stations.begin(), stations.end(), compY);
  for (unsigned int i = 0; i < stations.size() - 1; ++i) {
    for (unsigned int j = i + 1; stations[j].y == stations[i].y; ++j) {
      addEdge(stations[i].id, stations[j].id,
              stationsDistance(stations[i].x, stations[j].x));
    }
  }

  for (unsigned int i = 0; i <= m + 1; ++i) {
    dis[i] = INT32_MAX;
  }

  priority_queue<Edge> heap;
  heap.push(Edge(0, 0, 0));
  dis[0] = 0;

  while (heap.size()) {
    unsigned int now = heap.top().from;
    heap.pop();

    if (vis[now]) {
      continue;
    }
    vis[now] = true;

    for (auto i : graph[now]) {
      if (dis[i.to] > dis[now] + i.len) {
        dis[i.to] = dis[now] + i.len;
        heap.push(Edge(i.to, 0, dis[i.to]));
      }
    }
  }

  write(dis[m + 1] - 1);
  putchar('\n');

  return 0;
}