算法題「積雪清理」：除雪車路徑最短時間計算（圖論建模）

問題建模

城市道路為直線段，每條路雙向兩車道。除雪車：

• 除雪速度 20 km/h（清掃未清車道）。
• 行駛速度 50 km/h（已清車道）。
• 可在路口任意轉向、路末掉頭換車道。

車庫位於某道路線段上。求清掃所有車道並返回車庫的最短時間。

關鍵洞察

每條路長 L，雙車道總長 2L。最優策略：單向清掃至盡頭，掉頭返回，清掃另一車道，再返回車庫。無需重複清掃，總行程 = 所有道路長度之和 × 2（去程除雪 + 回程行駛）。

公式推導

設所有道路總長 S（單車道）。雙車道總長 2S。
除雪時間 = 2S / 20 = S/10 (h)。
回程行駛時間 = 2S / 50 = S/25 (h)。
總時間 = S/10 + S/25 = 7S/50 (h)。
換算：T = S × 3600 / 5000 = S / 20000 × 2 (h) → 代碼中 t = s/20000*2。

AC 代碼

#include <stdio.h>
#include <math.h>
int main() {
    double x1,y1,x2,y2, s=0, t;
    scanf("%*d %*d"); // 忽略車庫座標
    while (scanf("%lf %lf %lf %lf", &x1,&y1,&x2,&y2) != EOF) {
        s += sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
    }
    t = s / 20000 * 2; // 總小時數
    int m = (t - (int)t) * 60 + 0.5; // 四捨五入到分
    if (m == 60) printf("%02d:00\n", (int)t + 1);
    else printf("%02d:%02d\n", (int)t, m);
    return 0;
}

樣例驗證

Input:
0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000
Output: 03:55

三條路長度：√2×10000≈14142、20000、5000，總和 39142 m。
t = 39142/20000*2 ≈ 3.9142 h = 3h 54.85m → 03:55。