题解：P12192 [NOISG 2025 Prelim] Train Or Bus

· · 题解

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