题解：SP5465 DP - Deliver pizza

yanxu_cn · 2025-09-03 08:02:53 · 题解

简单题，一个源，多个终点，显然是单源最短路板子题。

由于显然所有的边的边权都是正的，所以使用 Dijkstra 即可。

注意到图是稀疏的，所以时间复杂度为 O(nm\log(nm))，空间复杂度为 O(nm) 可以非常轻松通过。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <functional>
#define endl '\n'
using namespace std;

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

struct Point {
    int x, y;
    Point(int x, int y) : x(x), y(y) {}
};

struct Node {
    int x, y, cost;
    Node(int x, int y, int cost) : x(x), y(y), cost(cost) {}
    bool operator>(const Node& other) const {
        return cost > other.cost;
    }
};

int n, m;
vector<string> grid;
vector<Point> buildings;

int getCost(char current, char neighbor) {
    if (current == 'X' || current == '$' || neighbor == 'X' || neighbor == '$') {
        return 2;
    }

    int h1 = current - '0';
    int h2 = neighbor - '0';
    int diff = abs(h1 - h2);

    if (diff > 1) return -1;
    if (diff == 0) return 1;
    return 3;
}

vector<int> dijkstra(int startX, int startY) {
    vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
    priority_queue<Node, vector<Node>, greater<Node>> pq;

    dist[startX][startY] = 0;
    pq.push(Node(startX, startY, 0));

    while (!pq.empty()) {
        Node node = pq.top();
        pq.pop();

        if (node.cost > dist[node.x][node.y]) continue;

        for (int i = 0; i < 4; i++) {
            int nx = node.x + dx[i];
            int ny = node.y + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

            int cost = getCost(grid[node.x][node.y], grid[nx][ny]);
            if (cost == -1) continue;

            int new_cost = node.cost + cost;
            if (new_cost < dist[nx][ny]) {
                dist[nx][ny] = new_cost;
                pq.push(Node(nx, ny, new_cost));
            }
        }
    }

    vector<int> result;
    for (const auto& building : buildings) {
        result.push_back(dist[building.x][building.y]);
    }
    return result;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        cin >> n >> m;
        grid.resize(n);
        buildings.clear();

        int startX = -1, startY = -1;

        for (int i = 0; i < n; i++) {
            cin >> grid[i];
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 'X') {
                    startX = i;
                    startY = j;
                    buildings.push_back(Point(i, j));
                } else if (grid[i][j] == '$') {
                    buildings.push_back(Point(i, j));
                }
            }
        }

        if (startX == -1) {
            cout << -1 << endl;
            continue;
        }

        vector<int> distances = dijkstra(startX, startY);

        bool impossible = false;
        for (int d : distances) {
            if (d == INT_MAX) {
                impossible = true;
                break;
            }
        }

        if (impossible) {
            cout << -1 << endl;
            continue;
        }

        int K = buildings.size();
        int total_mask = (1 << K);

        vector<int> subset_time(total_mask, 0);

        for (int mask = 1; mask < total_mask; mask++) {
            int total = 0;
            int max_d = 0;
            for (int i = 0; i < K; i++) {
                if (mask & (1 << i)) {
                    total += distances[i];
                    max_d = max(max_d, distances[i]);
                }
            }
            subset_time[mask] = 2 * total - max_d;
        }

        int ans = INT_MAX;
        int full_mask = total_mask - 1;

        for (int mask1 = 1; mask1 < total_mask; mask1++) {
            if ((mask1 & 1) == 0) continue;

            int mask2 = full_mask ^ mask1;
            int time1 = subset_time[mask1];
            int time2 = mask2 == 0 ? 0 : subset_time[mask2];

            ans = min(ans, max(time1, time2));
        }

        cout << ans << endl;
    }

    return 0;
}