抄近路描述琳琳每天要从家到车站，小区被道路分成许多正方形的块，共有N×M块，一般情况下，小区内的方块建有房屋，只能沿着附近的街道行走，有时方块表示公园，那么就可以直接穿过。 请你帮她计算一下从家到车站的最短距离。 输入第一行是N和M。注意，琳琳家坐标在方块(1,1)的西南角，车站在方块(M,N)的东北角。每个方块边长100米。接下来一行是整数K，表示可以对角线穿过的方块数，然后有K行，每行两个数，表示一个坐标。 输出输出最短距离，四舍五入到整数米。 样例输入3 231 13 21 2输出383提示0＜N,M≤1000 方块, 大佬
[ol][*]#include [i] [*]#include [*]#include [*]#include [*]#include [*]#include [u] [*]#include [u] [*]#include [i] [*] [*]using namespace std; [*] [*]struct Point { [*] int x, y; [*] Point(int x_, int y_) : x(x_), y(y_) {} [*] bool operator==(const Point& other) const { [*] return x == other.x && y == other.y; [*] } [*]}; [*] [*]namespace std { [*] template [*] struct hash { [*] size_t operator()(const Point& p) const { [*] return p.x * 1000 + p.y; [*] } [*] }; [*]} [*] [*]double calculateDistance(int x1, int y1, int x2, int y2, bool isPark) { [*] if (isPark) { [*] return sqrt(pow((x2 - x1) * 100, 2) + pow((y2 - y1) * 100, 2)); [*] } else { [*] return abs(x2 - x1) * 100 + abs(y2 - y1) * 100; [*] } [*]} [*] [*]double shortestPath(int N, int M, const unordered_set& parks) { [*] vector> dist(M + 1, vector(N + 1, INT_MAX)); [*] dist[1][1] = 0; [*] priority_queue, vector>, greater>> pq; [*] pq.push({0, Point(1, 1)}); [*] [*] int dx4[] = {-1, 1, 0, 0}; [*] int dy4[] = {0, 0, -1, 1}; [*] int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}; [*] int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1}; [*] [*] while (!pq.empty()) { [*] auto current = pq.top(); [*] pq.pop(); [*] double currentDist = current.first; [*] Point u = current.second; [*] [*] if (u.x == M && u.y == N) { [*] return currentDist; [*] } [*] [*] if (currentDist > dist[u.x][u.y]) { [*] continue; [*] } [*] [*] bool isPark = parks.find(u) != parks.end(); [*] [*] if (isPark) { [*] for (int i = 0; i = 1 && nx = 1 && ny = 1 && nx = 1 && ny > N >> M; [*] int K; [*] cin >> K; [*] unordered_set parks; [*] for (int i = 0; i > x >> y; [*] parks.insert(Point(x, y)); [*] } [*] [*] double distance = shortestPath(N, M, parks); [*] cout 复制代码
优先队列（堆优化）[ol]priority_queue, greater> pq;pq.push({0, start});while (!pq.empty()) { auto [dist, u] = pq.top(); pq.pop(); if (dist > distance[u.x][u.y]) continue; // 跳过已处理的节点 for (auto [v, w] : neighbors) { if (distance[v.x][v.y] > dist + w) { distance[v.x][v.y] = dist + w; pq.push({distance[v.x][v.y], v}); } }}[/ol]复制代码邻接表代替邻接矩阵 [ol]vector>> adj(N * M); // 邻接表for (int i = 0; i = 0 && nx = 0 && ny 复制代码双向Dijkstra或A*算法 [ol]// 双向Dijkstraunordered_set visited_start, visited_end;queue q_start, q_end;q_start.push(start); q_end.push(end);while (!q_start.empty() && !q_end.empty()) { expand(q_start, visited_start, visited_end); // 检查是否相遇 expand(q_end, visited_end, visited_start);}[/ol]复制代码
