题解：SP5465 DP - Deliver pizza

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