洛谷 P3831 - 做题记录

发表于 2021-07-01 本文字数： 1.2k 阅读时长 ≈ 4 分钟

洛谷 P3831 - 做题记录

原题链接

洛谷 P3831 [SHOI2012] 回家的路

题目信息

使用的算法

图论
最短路

难度

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

简化题意

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

思想方法

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

代码实现

保存交汇节点

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, 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];

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

当起点所在的坐标 $(x_{from}, y_{from})$ 时，如没有坐标为 $(x_{from}, y)$ 或 $(x, y_{from})$ 的交汇点时无法到达终点，因为无法通过交汇点到达目标（除非目标的任一坐标与起点相同），目标同理
即可想到使用 set 存储交汇点的 $(x, y)$ 坐标

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进行排序

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

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]));
    }
  }
}

最后，输出答案

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

完整代码

由于数据点没有 $-1$ 的情况，所以省略判断 $-1$

// 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;
}