题意分析

题目要求我们找到从第 $1$ 层到第 $M$ 层的一条路径，使得签署文件的总费用最小。具体规则如下：

1. 签署条件：
   • 第 $1$ 层的官员可以直接签署。
   • 其他层的官员签署的条件是：
     • 正下方楼层（$l-1$）的同号房间（$k$）已签署。
     • 同一楼层的相邻房间（$k-1$ 或 $k+1$）已签署。
2. 费用计算：
   • 每个官员签署时收取一定的费用（正整数）。
   • 总费用是所有签署官员的费用之和。
3. 输出要求：
   • 输出一条费用最小的路径，按访问顺序输出房间号（每行一个）。
   • 若有多条路径费用相同，输出任意一条即可。

解题思路

1. 图的建模：
   • 将每个官员（$l, k$）视为图中的一个节点。
   • 节点之间的边表示可以移动的条件：
     • 同一楼层的相邻房间（$k-1$ 或 $k+1$）。
     • 正下方楼层的同号房间（$l-1, k$）。
   • 边的权重是对应官员的签署费用。
2. 最短路径算法选择：
   • 由于所有边的权重为正，可以使用 Dijkstra算法 来找到单源最短路径。
   • 使用优先队列（最小堆）优化，每次选取当前费用最小的节点进行扩展。
3. 路径回溯：
   • 在计算最短路径时，记录每个节点的前驱节点。
   • 到达第 $M$ 层的任意房间后，回溯前驱节点，得到完整路径。

实现步骤

1. 输入处理：
   • 读取楼层数 $M$ 和每层房间数 $N$。
   • 读取每层每个官员的签署费用。
2. 初始化：
   • 使用优先队列存储待处理的节点（$floor, room, cost$）。
   • 初始化距离数组 $dist$，记录到达每个节点的最小费用。
   • 初始化前驱数组 $prev\_node$，记录路径。
3. Dijkstra算法：
   • 将第 $1$ 层的所有房间加入优先队列（初始费用为该房间的费用）。
   • 每次取出当前费用最小的节点，检查其相邻节点（同一楼层相邻房间和正下方同号房间）。
   • 如果找到更小的费用，更新距离并加入队列。
4. 路径回溯：
   • 找到第 $M$ 层中费用最小的房间。
   • 递归回溯前驱节点，输出路径上的房间号。

代码实现

#include <cstdio>
#include <queue>
#include <vector>
#include <climits>
#include <cstring>
using namespace std;

const int MAX_M = 101;
const int MAX_N = 501;

struct Node {
    int floor, room;
    long long cost;
    Node(int f, int r, long long c) : floor(f), room(r), cost(c) {}
    bool operator<(const Node& other) const {
        return cost > other.cost; // Min-heap
    }
};

int M, N;
int cost[MAX_M][MAX_N];
long long dist[MAX_M][MAX_N];
pair<int, int> prev_node[MAX_M][MAX_N];
bool visited[MAX_M][MAX_N];

const int dr[] = {-1, 1}; // 相邻房间的方向

void dijkstra() {
    priority_queue<Node> pq;
    memset(dist, -1, sizeof(dist));
    for (int k = 1; k <= N; ++k) {
        dist[1][k] = cost[1][k];
        pq.push(Node(1, k, dist[1][k]));
        prev_node[1][k] = make_pair(-1, -1);
    }
    
    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        int l = current.floor;
        int k = current.room;
        if (visited[l][k]) continue;
        visited[l][k] = true;
        
        if (l == M) {
            break;
        }
        
        // 检查同一楼层的相邻房间
        for (int i = 0; i < 2; ++i) {
            int nk = k + dr[i];
            if (nk >= 1 && nk <= N) {
                if (dist[l][nk] == -1 || dist[l][k] + cost[l][nk] < dist[l][nk]) {
                    dist[l][nk] = dist[l][k] + cost[l][nk];
                    prev_node[l][nk] = make_pair(l, k);
                    pq.push(Node(l, nk, dist[l][nk]));
                }
            }
        }
        
        // 检查正下方的房间
        if (l + 1 <= M) {
            int nl = l + 1;
            if (dist[nl][k] == -1 || dist[l][k] + cost[nl][k] < dist[nl][k]) {
                dist[nl][k] = dist[l][k] + cost[nl][k];
                prev_node[nl][k] = make_pair(l, k);
                pq.push(Node(nl, k, dist[nl][k]));
            }
        }
    }
}

void print_path(int l, int k) {
    if (l == -1) return;
    print_path(prev_node[l][k].first, prev_node[l][k].second);
    printf("%d\n", k);
}

int main() {
    scanf("%d %d", &M, &N);
    for (int l = 1; l <= M; ++l) {
        for (int k = 1; k <= N; ++k) {
            scanf("%d", &cost[l][k]);
        }
    }
    
    dijkstra();
    
    // 找到第M层中费用最小的房间
    long long min_cost = -1;
    int best_room = -1;
    for (int k = 1; k <= N; ++k) {
        if (dist[M][k] != -1 && (min_cost == -1 || dist[M][k] < min_cost)) {
            min_cost = dist[M][k];
            best_room = k;
        }
    }
    
    print_path(M, best_room);
    
    return 0;
}