题目描述给定一个平面图由M MM条线段组成每条线段有高度正整数线段仅在端点相交且不重叠。每条线段由两个端点编号1 11到N NN表示。一条路径定义为线段的序列L C 1 , L C 2 , … , L C k L_{C_1}, L_{C_2}, \ldots, L_{C_k}LC1,LC2,…,LCk满足k 1 k 1k1且C i ≠ C j C_i \neq C_jCiCj线段不重复相邻线段共享一个端点起点线段的某一端点是孤立端点不与其他线段相交终点线段的某一端点也是孤立端点。路径成本为k ⋅ Δ ∑ i 1 k − 1 ∣ height ( L C i ) − height ( L C i 1 ) ∣ k \cdot \Delta \sum_{i1}^{k-1} |\text{height}(L_{C_i}) - \text{height}(L_{C_{i1}})|k⋅Δi1∑k−1∣height(LCi)−height(LCi1)∣其中Δ \DeltaΔ是给定开销。求所有路径中的最小成本。输入格式第一行为测试用例数l ll。每个测试用例第一行为三个整数M MM、N NN、Δ \DeltaΔ。接下来M MM行每行三个整数表示一条线段的两端点编号及其高度。输出格式对于每个测试用例输出一行即最小路径成本。样例输入2 8 9 25 1 2 1 8 9 10 7 8 9 1 4 2 4 5 20 1 3 9 3 5 9 5 6 8 6 21 1 2 1 1 4 2 4 5 20 1 3 9 3 5 9 5 6 8输出51 93题目分析本题可建模为图论问题。每条线段是一个节点相邻线段共享端点之间连边边权为高度差绝对值加上Δ \DeltaΔ但Δ \DeltaΔ是在路径总成本中按线段个数乘以Δ \DeltaΔ而非每条边加Δ \DeltaΔ。路径起点和终点必须是孤立端点所在的线段。我们需要找到从任意起点线段到任意终点线段的最短路径其中路径长度k kk的计算方式特殊总成本为k ⋅ Δ ∑ k \cdot \Delta \sumk⋅Δ∑高度差。一种方法是将每个端点作为图中的节点线段作为边但路径成本涉及线段的个数。我们可以将问题转化为在“线段图”上的最短路径其中节点为线段边权为高度差绝对值另外每走一条边进入一个新线段增加Δ \DeltaΔ但起点线段本身也计1 11个Δ \DeltaΔ。因此我们可以对每条线段计算从起点到该线段的最小成本状态为(线段, 是否已访问过)但由于线段不重复直接DFS \texttt{DFS}DFS枚举所有路径即可M ≤ 200 M \le 200M≤200N ≤ 400 N \le 400N≤400。解题思路建立端点与线段的关联对于每个端点存储所有与该端点相连的线段即线段端点。对每个可能的起点线段即该线段有一个端点只属于它自己即度为1 11的端点执行深度优先搜索DFS \texttt{DFS}DFS当前线段i当前路径长度length线段数上一条线段高度previous当前总成本cost。若当前线段有一个端点度为1 11且length 2则更新最小成本。否则遍历与当前线段共享端点的其他线段若未访问过则递归。剪枝若当前成本已超过已知最优解则提前返回。输出最小成本。复杂度分析每个状态为 (线段, 访问位掩码) 的组合但M ≤ 200 M \le 200M≤200DFS \texttt{DFS}DFS可能枚举所有路径但通过剪枝和路径数量有限可接受。代码实现// Least Path Cost// UVa ID: 685// Verdict: Accepted// Submission Date: 2017-06-10// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structedge{intstart,end,height;};intM,N,D;vectorvectoredgeedges(410,vectoredge());vectorintvisited(410);intminCost-1;voiddfs(inti,intlength,intprevious,intcost){if(minCost!-1length2costminCost)return;if(previous!-1length2edges[i].size()1){if(minCost-1)minCostcost;elseminCostmin(minCost,cost);}else{for(autoe:edges[i]){if(visited[e.end])continue;visited[i]1;if(previous-1)dfs(e.end,length1,e.height,costD);elsedfs(e.end,length1,e.height,costDabs(e.height-previous));visited[i]0;}}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;intstart,end,height;cincases;for(intc1;ccases;c){cinMND;for(inti1;iN;i)edges[i].clear();for(inti1;iM;i){cinstartendheight;edges[start].push_back(edge{start,end,height});edges[end].push_back(edge{end,start,height});}minCost-1;for(inti1;iN;i){if(edges[i].size()!1)continue;fill(visited.begin(),visited.end(),0);dfs(i,0,-1,0);}coutminCost\n;}return0;}总结本题通过将线段视为图节点利用深度优先搜索枚举所有可能的路径并剪枝优化求解最小路径成本。关键点包括正确建模路径的起点和终点度为1 11的端点。路径成本包括线段个数乘以Δ \DeltaΔ和高度差之和。使用DFS \texttt{DFS}DFS枚举所有简单路径线段不重复并剪枝。该解法适用于M ≤ 200 M \le 200M≤200的中等规模图。
