《雪道清扫问题》解题思路

1. 问题本质

• 中国邮路问题变种：需要遍历所有双向道路的最短路径
• 核心约束：
  • 每条道路必须被清扫两次（往返方向各一次）
  • 不同行驶速度影响总时间（清扫20km/h vs 空驶50km/h）

2. 关键结论

• 最优解公式：

  总时间 = (所有道路总长度 × 2) / 清扫速度
  

• 原因：可以设计环形路线使空驶时间为0

3. 计算步骤

1. 输入处理：

   • 读取车库坐标（起点）
   • 逐行读取每条道路的起点和终点坐标

2. 距离计算：

   • 对每条道路计算其长度（欧几里得距离公式）：

     距离 = √[(x₂-x₁)² + (y₂-y₁)²]
     

3. 总时间计算：

   • 总清扫距离 = 所有道路长度之和 × 2
   • 总时间（小时） = 总清扫距离 / 20000（20km/h=20000m/h）

4. 时间格式转换：

   • 小时部分取整数
   • 小数部分×60后四舍五入得分钟数
   • 处理分钟进位（≥60时小时+1）

4. 边界情况处理

• 四舍五入：使用round函数确保精确到分钟
• 单位统一：所有计算保持米和小时单位
• 道路可达性：题目保证所有道路连通，无需额外检查

5. 复杂度分析

• 时间复杂度：O(M)（M为道路数量）
• 空间复杂度：O(M)（存储所有道路）

实现提示

1. 距离计算函数

#include <cmath> // 必须包含的头文件

// 计算两点间距离（单位：米）
double calcDistance(double x1, double y1, double x2, double y2) {
    return sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2));
}

2. 时间转换代码

#include <iomanip> // 控制输出格式

// 输入：总时间（单位：小时）
// 输出："时:分"格式字符串
std::string formatTime(double totalHours) {
    int hours = static_cast<int>(totalHours);
    int minutes = static_cast<int>(round((totalHours - hours) * 60));
    
    // 处理分钟进位（如3.999小时→4:00）
    if(minutes >= 60) {
        hours += 1;
        minutes = 0;
    }
    
    // 格式化为两位数分钟（如3:5→03:05）
    std::ostringstream oss;
    oss << hours << ":" << std::setw(2) << std::setfill('0') << minutes;
    return oss.str();
}

标程

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

struct Point {
    double x, y;
};

// 计算两点间距离（米）
double calcDistance(Point a, Point b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

int main() {
    Point hangar;
    cin >> hangar.x >> hangar.y;
    
    vector<pair<Point, Point> > roads;  // C++98 需要加空格 `> >`
    double totalLength = 0;
    
    // 读取所有道路
    Point start, end;
    while (cin >> start.x >> start.y >> end.x >> end.y) {
        roads.push_back(make_pair(start, end));  // C++98 用 `push_back(make_pair(...))` 替代 `emplace_back`
        totalLength += calcDistance(start, end);
    }
    
    /* 
    关键计算：
    1. 必须清扫的总距离 = 所有道路长度 × 2（双向）
    2. 最优情况下不需要额外空驶（可以设计环形路线）
    3. 总时间 = 清扫总距离 / 清扫速度
    */
    double totalHours = (totalLength * 2) / 20000.0;  // 20 km/h = 20000 m/h
    
    // 转换为小时和分钟（四舍五入）
    int hours = static_cast<int>(totalHours);
    int minutes = static_cast<int>(round((totalHours - hours) * 60));
    
    // 处理分钟进位
    if (minutes >= 60) {
        hours += 1;
        minutes -= 60;
    }
    
    cout << hours << ":" << setw(2) << setfill('0') << minutes << endl;
    
    return 0;
}