用C语言搞定PTA数据结构7-1天梯地图：迪杰斯特拉算法实战与避坑指南

从零实现PTA天梯地图双权重迪杰斯特拉算法全解析当面对PTA数据结构7-1天梯地图这类双权重图的最短路径问题时许多初学者会陷入算法选择的困境。本文将彻底拆解如何用C语言实现这一经典题目不仅教你写出能AC的代码更重要的是掌握算法改造的思维方法。1. 问题重难点剖析这道题的核心在于处理带有两个权重距离和时间的有向图并需要满足以下特殊条件双最优路径输出需分别计算最快路径和最短距离路径次级条件处理当多条路径时间相同时选择其中距离最短的当多条路径距离相同时选择经过节点最少的路径还原需要记录并输出完整路径节点序列常见误区包括// 错误示例仅存储单一权重 typedef struct { int weight; // 无法同时表示时间和距离 // ... } Edge;2. 数据结构设计关键正确的数据结构设计是解题的基础。我们需要2.1 图的表示采用邻接矩阵存储双权重信息#define INF 0x3f3f3f3f typedef struct { int length; // 道路长度 int time; // 通行时间 } Edge; Edge graph[MAX_N][MAX_N]; // 邻接矩阵2.2 路径信息记录需要扩展传统迪杰斯特拉算法的存储结构typedef struct { int prev; // 前驱节点 int total_dist; // 累计距离 int total_time; // 累计时间 int node_count; // 节点计数用于距离相同时判断 } PathInfo;3. 算法改造实战标准迪杰斯特拉算法需要针对题目需求进行两处关键改造3.1 时间优先的最短路径void dijkstra_time(int start, int n, PathInfo time_path[]) { int visited[MAX_N] {0}; // 初始化 for (int i 0; i n; i) { time_path[i].total_time INF; time_path[i].total_dist INF; time_path[i].prev -1; time_path[i].node_count 0; } time_path[start].total_time 0; time_path[start].total_dist 0; time_path[start].node_count 1; for (int i 0; i n; i) { int u -1; // 找出当前未访问的最小时间节点 for (int j 0; j n; j) { if (!visited[j] (u -1 || time_path[j].total_time time_path[u].total_time)) u j; } if (time_path[u].total_time INF) break; visited[u] 1; // 松弛操作 for (int v 0; v n; v) { if (graph[u][v].time INF) continue; int new_time time_path[u].total_time graph[u][v].time; int new_dist time_path[u].total_dist graph[u][v].length; if (new_time time_path[v].total_time) { // 发现更优时间路径 time_path[v].total_time new_time; time_path[v].total_dist new_dist; time_path[v].prev u; time_path[v].node_count time_path[u].node_count 1; } else if (new_time time_path[v].total_time new_dist time_path[v].total_dist) { // 时间相同但距离更短 time_path[v].total_dist new_dist; time_path[v].prev u; time_path[v].node_count time_path[u].node_count 1; } } } }3.2 距离优先的最短路径void dijkstra_distance(int start, int n, PathInfo dist_path[]) { int visited[MAX_N] {0}; // 初始化与时间优先类似省略部分代码 // ... for (int i 0; i n; i) { int u -1; // 找出当前未访问的最小距离节点 for (int j 0; j n; j) { if (!visited[j] (u -1 || dist_path[j].total_dist dist_path[u].total_dist)) u j; } if (dist_path[u].total_dist INF) break; visited[u] 1; // 松弛操作 for (int v 0; v n; v) { if (graph[u][v].length INF) continue; int new_dist dist_path[u].total_dist graph[u][v].length; int new_time dist_path[u].total_time graph[u][v].time; int new_count dist_path[u].node_count 1; if (new_dist dist_path[v].total_dist) { // 发现更短距离路径 dist_path[v].total_dist new_dist; dist_path[v].total_time new_time; dist_path[v].prev u; dist_path[v].node_count new_count; } else if (new_dist dist_path[v].total_dist new_count dist_path[v].node_count) { // 距离相同但节点数更少 dist_path[v].total_time new_time; dist_path[v].prev u; dist_path[v].node_count new_count; } } } }4. 路径还原技巧获得最优路径后需要从终点回溯到起点void reconstruct_path(int end, PathInfo path[], int result[], int *count) { int current end; *count 0; // 反向存储路径 while (current ! -1) { result[(*count)] current; current path[current].prev; } // 反转路径数组 for (int i 0; i *count / 2; i) { int temp result[i]; result[i] result[*count - 1 - i]; result[*count - 1 - i] temp; } }5. 常见调试陷阱在实现过程中以下几个问题需要特别注意初始化问题// 错误示例忘记初始化node_count time_path[start].node_count 1; // 必须显式初始化边界条件处理// 处理没有路径的情况 if (path[end].total_time INF) { printf(No path exists\n); return; }输入数据读取// 读取道路信息时的常见错误 scanf(%d %d %d %d %d, v1, v2, one_way, len, time); if (one_way 0) { // 双向道路需要设置两个方向 graph[v2][v1].length len; graph[v2][v1].time time; }路径比较逻辑// 比较两条路径是否完全相同时的常见错误 int is_same_path 1; for (int i 0; i time_count; i) { if (time_path[i] ! dist_path[i] || time_count ! dist_count) { is_same_path 0; break; } }6. 性能优化建议当节点数N较大时接近题目上限500可以考虑以下优化优先队列优化// 使用最小堆替代线性搜索 typedef struct { int node; int time; int dist; } QueueItem; // 比较函数 int cmp_time(const void *a, const void *b) { return ((QueueItem*)a)-time - ((QueueItem*)b)-time; }稀疏图优化// 改用邻接表存储 typedef struct Node { int to; int length; int time; struct Node *next; } Node; Node *adj_list[MAX_N]; // 邻接表头指针数组提前终止// 当目标节点出队时提前终止 if (u target) break;7. 完整解决方案框架以下是整合各模块后的程序框架#include stdio.h #include string.h #define MAX_N 505 #define INF 0x3f3f3f3f // 数据结构定义省略 // 函数声明省略 int main() { int N, M; scanf(%d %d, N, M); // 初始化图 // ... // 读取道路信息 // ... int start, end; scanf(%d %d, start, end); PathInfo time_path[MAX_N], dist_path[MAX_N]; dijkstra_time(start, N, time_path); dijkstra_distance(start, N, dist_path); int time_route[MAX_N], dist_route[MAX_N]; int time_count 0, dist_count 0; reconstruct_path(end, time_path, time_route, time_count); reconstruct_path(end, dist_path, dist_route, dist_count); // 输出结果 // ... return 0; }在实际编码时建议先实现基本功能并通过样例测试再逐步添加次级条件判断最后进行边界条件测试和性能优化。这种分阶段实现的策略可以有效降低调试难度。