铲雪车(snow)

形式化题目

给定一个无向图，代表城市的街道。图中给出了铲雪车的起点坐标 $(x_0, y_0)$ ，以及若干条街道的起点和终点坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$ 。每条街道都是笔直的，且都是“双向一个车道”（即双向单车道，一条街道有两个相反方向的车道）。铲雪车要铲净所有车道（即每条街道的正反两个方向都要走一次），最后回到起点，求最短需要的时间。铲雪车在工作时（铲雪）速度为 $20\text{ km/h}$ ，如果不铲雪（在没雪的路上空驶）速度为 $50\text{ km/h}$ 。输出所需的时间，格式为 小时:分钟，其中分钟要四舍五入到整数且不足两位时补齐两位。

正解

思路

这道题表面上看似一道复杂的“中国邮递员问题（Chinese Postman Problem）”，实则是一个被“双向单车道”和“空载速度 50 km/h”这两个条件包装过的欧拉回路模型题。

题目中的关键句是：“所有街道都是双向一个车道”。这意味着如果我们把图看作一个有向图，那么每一条给出的街道，实际上就是两条连接两点但方向相反的有向边。

在这样的有向图中，无论原来的无向图有多少个度数为奇数的顶点，在转成有向图后，每一个顶点的“入度”和“出度”一定是相等的（因为每连出一条有向边，必定有一条反向的入边）。
题目又保证了“铲雪车从起点一定可以到达任何街道”，说明该图是强连通的。

这两个条件（入度等于出度，且强连通）恰好是有向图存在欧拉回路的充要条件。存在欧拉回路，意味着铲雪车完全可以一笔画走遍所有的有向边（即每一条车道），不重复且不遗漏地完成铲雪任务，并最终回到起点。因此，根本不需要像求解一般的中国邮递员问题那样去找奇度点并进行“奇度点配对”（因为所有的边都要走正反各一次），也根本不会发生以 $50\text{ km/h}$ 的速度空驶的情况（所有的路程都是在铲雪，速度全部为 $20\text{ km/h}$ ）。

解题步骤大大简化：

计算所有给定街道的单向直线距离（欧几里得距离）之和 total_distance（单位为米）。
因为是双向单车道，铲雪车走过的总路程就是所有街道单向距离之和的 $2$ 倍，即 2 * total_distance 米。
铲雪速度为 $20\text{ km/h}$ ，即 $20000\text{ m/h}$ 。
总耗时（小时）为 $\frac{2 \times \text{total\_distance}}{20000} = \text{total\_distance} \times 0.0001$ ；换算成分钟则是 $\text{total\_distance} \times 0.006$ 。
将分钟数四舍五入到最近的整数，再换算成 小时:分钟 格式输出。注：输入的起点坐标 $(x_0, y_0)$ 对最短时间完全没有影响，仅读取消费掉即可。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 15:03
# update_at: 2026-10-08 15:03

import sys
from math import floor, hypot

SPEED = 20000  # 铲雪时速度 20 km/h，换算成米/小时


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    start_x, start_y = next(data), next(data)  # 停车点坐标，对最短时间没有影响

    # 每条街道给出 4 个整数 x1 y1 x2 y2；同一个迭代器连取四次就按街道分好组。
    # 街道是双向单车道，拆成一正一反两条有向边后各点入度=出度，图有欧拉回路，
    # 铲雪车能一路铲雪走遍全部车道再回起点，所以总路程 = 单向长度之和 × 2。
    quads = zip(data, data, data, data)  # 迭代器连取四次 => 每项是一条街道的 (x1,y1,x2,y2)
    one_way = sum(hypot(x2 - x1, y2 - y1) for x1, y1, x2, y2 in quads)

    minutes = floor(one_way * 2 / SPEED * 60 + 0.5)  # 总用时换算成分钟，四舍五入
    print(f"{minutes // 60}:{minutes % 60:02d}")


if __name__ == "__main__":
    solve()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 15:03
 * update_at: 2026-10-08 15:03
 */
// 一本通 1374《铲雪车(snow)》
// 每条街道都是双向单车道，拆成一正一反两条有向边后每个顶点入度=出度，
// 又保证"从起点可达任何街道"（连通），所以图存在欧拉回路：
// 铲雪车能一路铲着雪走遍所有车道再回到起点，全程 20 km/h，不会有 50 km/h 的空驶。
// 答案 = 所有街道长度之和 × 2 ÷ 20000 小时（街道按双车道各走一次）。
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

double total_distance; // 所有街道的单向长度之和，单位米

// 读入停车点坐标（题意用不到，只按格式消费）与全部街道端点，累加街道长度
void read_input() {
    ll start_x, start_y;
    if (!(cin >> start_x >> start_y)) return;

    ll x1, y1, x2, y2;
    while (cin >> x1 >> y1 >> x2 >> y2) {
        double dx = x1 - x2;
        double dy = y1 - y2;
        total_distance += sqrt(dx * dx + dy * dy);
    }
}

// 时间(分钟) = 总路程(米) × 2 ÷ 20000(米/小时) × 60 = total_distance × 0.006，
// 四舍五入到整分钟，再按 小时:分钟 输出（分钟补两位零）
void solve() {
    ll total_minutes = floor(total_distance * 0.006 + 0.5);
    ll hour = total_minutes / 60;
    ll minute = total_minutes % 60;
    cout << hour << ":" << setfill('0') << setw(2) << minute << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度: $\mathcal{O}(N)$ ，其中 $N$ 是给出的街道数量。只需要一次遍历读取输入数据并累加距离计算。
空间复杂度: $\mathcal{O}(1)$ ，只需保存累计长度和当前读取的坐标点即可。

总结

为什么不需要奇度点配对：这是本题最容易踩的坑。如果是“单车道”街道网络，且要求走遍所有边并回到起点，那么图的奇度点就不为 $0$ ，这就变成了经典的“中国邮递员问题”，需要求最短路来做奇度点匹配，走回头路时便会用到 $50\text{ km/h}$ 的空驶速度。但本题题面强调了“所有街道都是双车道”，这就相当于每条边必定走两次（一正一反），把奇度点全都自然地变成了出入度相等的点。因此，“不需要任何配对空跑，总路程就是所有边长的两倍”才是正解。
数据量级与变量类型：当给出的街道数目多、坐标范围大时（如大数据点），计算出的距离和累计的时间（尤其是分钟总数）可能会很大。比如测试点中有的总耗时达到上万小时。因此，在存储坐标和分钟总数时，应使用 $64$ 位整数（如 C++ 中的 long long）来避免溢出。
四舍五入：最后将浮点型分钟数转为整数时，需要正确使用四舍五入。C++ 中可以用 floor(minutes + 0.5) 或者是 round(minutes)，特别要注意部分小数可能处于四舍五入的边界附近。
输出格式控制：最终输出结果必须以 时:分 的格式，当分钟数小于 $10$ 时必须用前导零补齐两位，即 %02d 格式。

目录

形式化题目

正解

思路

代码

复杂度

总结