分析： 首先，如果你认为是图论或者其他算法，我并不认为做不出来。但至少DP是能做的。 因为虽然题目各方面都是与图有关，但其实仔细想想，这个图已经被固定了，唯一有变化的就是边权。不难想到很多DP模型都是这个样子，满足统一的特征或者结构，但具体的数值有所不同。最重要的是，这个图很明显是一个近似于一条链的东西。 由此，我们猜想可以用DP来做。 最开始必须明确一个基本性质：任何一个点的度数都必