自动搬运

查看原文

来自洛谷，原作者为

	dg114514 qq 8268838 欢迎加 || 壶关条件 U540059

搬运于2025-08-24 23:13:34，当前版本为作者最后更新于2025-04-14 19:18:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

bushi 这能交题解？
给红题写题解自然得写好一点。
思路：使用贪心法，将每个选择上的两种方式取最小时间累加即可。
证明：使用反证法。假设有路径 $p'$ 的总时间小于贪心选出的最优路径 $p$ 的总时间。那么显然，$p'$ 一定要有某次选择的时间短于 $p$ 才能优于 $p$。但是 $p$ 基于贪心，在所有选择路上选择的都是时间最小的方式。所以 $p'$ 不存在，$p$ 为最优路径。