当前位置：首页 > news >正文

UVa 685 Least Path Cost

news 2026/7/17 21:05:26

题目描述

给定一个平面图，由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 > 1k>1，且C i ≠ C j C_i \neq C_jCi=Cj（线段不重复）；
相邻线段共享一个端点；
起点线段的某一端点是孤立端点（不与其他线段相交），终点线段的某一端点也是孤立端点。

路径成本为：
k ⋅ Δ + ∑ i = 1 k − 1 ∣ height ( L C i ) − height ( L C i + 1 ) ∣ k \cdot \Delta + \sum_{i=1}^{k-1} |\text{height}(L_{C_i}) - \text{height}(L_{C_{i+1}})|k⋅Δ+i=1∑k−1∣height(LCi)−height(LCi+1)∣
其中Δ \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≤200，N ≤ 400 N \le 400N≤400。

解题思路

建立端点与线段的关联：对于每个端点，存储所有与该端点相连的线段（即线段端点）。
对每个可能的起点线段（即该线段有一个端点只属于它自己，即度为1 11的端点），执行深度优先搜索（DFS \texttt{DFS}DFS）：
- 当前线段i，当前路径长度length（线段数），上一条线段高度previous，当前总成本cost。
- 若当前线段有一个端点度为1 11且length >= 2，则更新最小成本。
- 否则，遍历与当前线段共享端点的其他线段，若未访问过，则递归。
剪枝：若当前成本已超过已知最优解，则提前返回。
输出最小成本。

复杂度分析

每个状态为 (线段, 访问位掩码) 的组合，但M ≤ 200 M \le 200M≤200，DFS \texttt{DFS}DFS可能枚举所有路径，但通过剪枝和路径数量有限，可接受。

代码实现

// Least Path Cost// UVa ID: 685// Verdict: Accepted// Submission Date: 2017-06-10// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structedge{intstart,end,height;};intM,N,D;vector<vector<edge>>edges(410,vector<edge>());vector<int>visited(410);intminCost=-1;voiddfs(inti,intlength,intprevious,intcost){if(minCost!=-1&&length>=2&&cost>minCost)return;if(previous!=-1&&length>=2&&edges[i].size()==1){if(minCost==-1)minCost=cost;elseminCost=min(minCost,cost);}else{for(autoe:edges[i]){if(visited[e.end])continue;visited[i]=1;if(previous==-1)dfs(e.end,length+1,e.height,cost+D);elsedfs(e.end,length+1,e.height,cost+D+abs(e.height-previous));visited[i]=0;}}}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases=0;intstart,end,height;cin>>cases;for(intc=1;c<=cases;c++){cin>>M>>N>>D;for(inti=1;i<=N;i++)edges[i].clear();for(inti=1;i<=M;i++){cin>>start>>end>>height;edges[start].push_back(edge{start,end,height});edges[end].push_back(edge{end,start,height});}minCost=-1;for(inti=1;i<=N;i++){if(edges[i].size()!=1)continue;fill(visited.begin(),visited.end(),0);dfs(i,0,-1,0);}cout<<minCost<<'\n';}return0;}