✅ PAT 甲级题目讲解1003《Emergency》摘要本文详细讲解 PAT 甲级 1003《Emergency》题目的解法。该题要求在带权无向图中求解从起点到终点的最短路径数量以及所有最短路径中能召集的最大救援队总数。文章采用Dijkstra 算法作为核心框架扩展维护cnt[]路径计数与maxr[]最大点权和两个状态数组并提供链式前向星建图、完整 C 代码、常见错误总结与复杂度分析。 题目简介这是一道带权无向图的最短路径综合题。已知每个城市分布有若干救援队城市之间通过无向边相连每条边有正整数距离我们的目标是从起点城市C1出发以最快速度赶往目的地城市C2并沿途尽可能召集最多的救援队人员。要求输出从C1到C2的最短路径数量所有最短路径中能召集到的最多救援队总数。关键建模点图中点表示城市边表示道路要求最短路径条数 路径上的最大点权和 —— 典型的Dijkstra 拓展模型。 样例分析输入样例5 6 0 2 1 2 1 5 3 0 1 1 0 2 2 0 3 1 1 2 1 2 4 1 3 4 1含义解释5个城市6条道路起点为城市0终点为城市2每个城市救援队数量分别为1, 2, 1, 5, 3道路(u, v, l)表示无向边u↔vu \leftrightarrow vu↔v长度为lll。图结构如下1 0-----1 | \ | 1 | 2\ |1 | \ 3 2 \ | 1\ |1 \ | 4可能路径直接 0 → 2总长 2救援队数量 1 1 20 → 1 → 2总长 112救援队数量 1 2 1 4共 2 条最短路径其中最大救援队数量为4。输出2 4 解题思路 本题建模为最短路径 路径统计 点权最大值基本框架为Dijkstra 算法并在基础上维护两组额外信息cnt[v]: 从起点到城市v的最短路径条数maxr[v]: 到城市v的最短路径中最多可召集的救援队数。 变量说明变量名类型含义nint城市数mint道路数c1,c2int起点、终点城市编号r[i]int第i个城市的救援队数目head[i]int城市i的邻接链表头指针to[k]int第k条边指向的城市编号nt[k]int第k条边的下一条边链式前向星val[k]int第k条边的长度dis[i]int起点到城市i的最短距离cnt[i]int起点到城市i的最短路径数量maxr[i]int起点到城市i的路径中最多可召集救援队vis[i]bool城市i是否已访问✅ Step 1建图处理链式前向星采用链式前向星建图可高效存储无向边voidadde(intx,inty,intw){// 建立 x - y权值为 w 的边to[k]y;// 目标城市编号nt[k]head[x];// 插入链表头head[x]k;// 设置结点 x 第一条出度边为 kval[k]w;// 权重/道路长度}注意每条无向边需调用adde(x,y,w)和adde(y,x,w)各一次。✅ Step 2Dijkstra 模板扩展通过贪心策略每次选出当前未访问的、距离起点最近的城市u然后尝试更新其所有邻接点vvoidd(ints){// 求从 s 出发到图中任意其他点的最短路dis[s]0;// 初始化起点最短距离为 0maxr[s]r[s];// 初始可收集的救援队cnt[s]1;// 起点到自身的路径数为 1for(inti0;in;i){// n 轮选点intu-1,mindinf;// u 记录选取最近点mind 记录最近距离for(intj0;jn;j){// 遍历 n 个点if(!vis[j]dis[j]mind){// 找出未访问点中距离起点最近的点更新 uuj;minddis[j];}}if(u-1)break;// 上面 for() 执行完没找到合适点 - 所有点已访问完vis[u]1;// 标记所选点被访问✅ Step 3松弛操作 统计路径信息对于每个u → v的边根据新路径是否更优进行三种情况判断。 最短路径的数量统计设cnt[v]表示从起点到城市v的最短路径条数。初始时cnt[s] 1表示从起点到自己有 1 条路径若发现从u → v得到一个更短路径则更新为cnt[v]:cnt[u] cnt[v] : cnt[u]cnt[v]:cnt[u]若从u → v的路径长度等于当前最短路径即dis[u] l dis[v]则说明又找到一条等长的最短路径cnt[v]:cnt[v]cnt[u] cnt[v] : cnt[v] cnt[u]cnt[v]:cnt[v]cnt[u]路径上的最大救援队数统计设maxr[v]表示从起点到城市v的最短路径中能召集到的最大救援队数。初始时maxr[s] r[s]即起点自身的救援队若从u → v得到更短路径maxr[v]:maxr[u]r[v] maxr[v] : maxr[u] r[v]maxr[v]:maxr[u]r[v]若路径等长但救援队数更大则更新为maxr[v]:max⁡(maxr[v], maxr[u]r[v]) maxr[v] : \max(maxr[v],\ maxr[u] r[v])maxr[v]:max(maxr[v],maxr[u]r[v]) 小结路径枚举 状态扩展每访问一个城市u我们遍历其所有邻接边若dis[u] l dis[v]说明发现更短路径更新所有信息若dis[u] l dis[v]说明是等长路径需要更新路径条数与点权最大值若更长则忽略。这些逻辑嵌套于 Dijkstra 算法核心循环中实现。for(intjhead[u];j;jnt[j]){// j: 枚举 u 的所有邻接边intvto[j],lval[j];// v: 所有与 u 邻接的点l: u - v 的权值inttdis[u]l;// 从起点到 v 的当前路径长度if(tdis[v]){// 若当前路径更短dis[v]t;// 更新最短路径maxr[v]maxr[u]r[v];// 更新当前路径最大救援队数量是上一步加该步的总和cnt[v]cnt[u];// 更新当前路径最短路径数量等于上一步最短路径数}elseif(tdis[v]){// 路径长度相等cnt[v]cnt[u];// 多 cnt[u] 条路径maxr[v]max(maxr[v],maxr[u]r[v]);// 尝试更新最多救援队数量}}}}✅ 完整代码#includebits/stdc.husingnamespacestd;constintmaxn250005;constintinfINT_MAX;intn,m,c1,c2,r[505];inthead[505],to[maxn],nt[maxn],val[maxn],k;intdis[505],cnt[505],maxr[505];boolvis[505];voidadde(intx,inty,intw){// 建立 x - y权值为 w 的边to[k]y;// 目标城市编号nt[k]head[x];// 插入链表头head[x]k;// 设置结点 x 第一条出度边为 kval[k]w;// 权重/道路长度}voidd(ints){// 求从 s 出发到图中任意其他点的最短路dis[s]0;// 初始化起点最短距离为 0maxr[s]r[s];// 初始可收集的救援队cnt[s]1;// 起点到自身的路径数为 1for(inti0;in;i){// n 轮选点intu-1,mindinf;// u 记录选取最近点mind 记录最近距离for(intj0;jn;j){// 遍历 n 个点if(!vis[j]dis[j]mind){// 找出未访问点中距离起点最近的点更新 uuj;minddis[j];}}if(u-1)break;// 上面 for() 执行完没找到合适点 - 所有点已访问完vis[u]1;// 标记所选点被访问// 遍历 u 所有邻接边尝试松弛for(intjhead[u];j;jnt[j]){// j: 枚举 u 的所有邻接边intvto[j],lval[j];// v: 所有与 u 邻接的点l: u - v 的权值inttdis[u]l;// 从起点到 v 的当前路径长度if(tdis[v]){// 若当前路径更短dis[v]t;// 更新最短路径maxr[v]maxr[u]r[v];// 更新当前路径最大救援队数量是上一步加该步的总和cnt[v]cnt[u];// 更新当前路径最短路径数量等于上一步最短路径数}elseif(tdis[v]){// 路径长度相等cnt[v]cnt[u];// 多 cnt[u] 条路径maxr[v]max(maxr[v],maxr[u]r[v]);// 尝试更新最多救援队数量}}}}intmain(){scanf(%d %d %d %d,n,m,c1,c2);for(inti0;in;i){scanf(%d,r[i]);dis[i]inf;// 初始化为不可达}while(m--){intx,y,l;scanf(%d %d %d,x,y,l);// 无向图双向建边adde(x,y,l);adde(y,x,l);}// Dijkstra 求最短路径 路径数 最大点权和d(c1);// 输出答案路径条数 最大救援队数printf(%d %d,cnt[c2],maxr[c2]);return0;} 常见错误提醒错误类型具体表现没有双向建边只调用一次adde(x,y,l)会导致图不连通忘记初始化dis[i]导致最短路径判断错误忽略路径相等情况只处理t dis[v]忽略t dis[v]的统计逻辑maxr 更新顺序错误忘记取max(...)直接累加错误没有标记访问vis[i]未标记会导致死循环或重复访问✅ 总结归纳 核心算法本题为典型的单源最短路径扩展题采用 Dijkstra 算法 路径计数 点权最大值维护图采用链式前向星高效建图避免邻接矩阵空间浪费。⏱️ 复杂度分析时间复杂度O(n2m)\mathcal{O}(n^2 m)O(n2m)其中n≤500n \leq 500n≤500m≤n2m \leq n^2m≤n2空间复杂度O(nm)\mathcal{O}(n m)O(nm)。 思维拓展若将图中边权改为负数如何处理Dijkstra 不再适用需使用 Bellman-Ford 或 SPFA如果要求输出所有路径的具体路径信息可通过pre[v]记录前驱链 DFS 构建若加入“最短路径中最少经过节点数”要求如何处理可额外记录step[v]数组统计路径长度。