思路与算法

每条街的两个方向各有一条要清雪的车道。把双向街道看成两条反向有向边，所有交叉口都满足入度=出度，且题目保证停车点可以到达所有街道，因此存在从停车点出发再回来的欧拉回路。它恰好清扫全部车道一次，不需要额外空跑。道路中心线总长为S米，需清扫2S米，以20千米/小时计算，总时间为3S/500分钟。每条线段长为√((x1−x2)²+(y1−y2)²)。标程用放大后的整数平方根给出长度上下界，必要时加倍精度，直到上下界舍入到同一分钟。

正确性说明

任何合法方案至少要把每条车道走一遍，因此路程不小于2S。连通有向图所有点入度等于出度，欧拉回路能达到该下界，所以最短时间就是清扫2S所用时间。放大整数平方根h满足h≤scale·长度<h+1，累加后仍给出总长的可靠区间。只有区间两端确定同一舍入分钟时才输出，故不会因巨大坐标或分钟边界附近的舍入产生浮点错误。全部长度为整数时直接处理精确值；含非平方根时非负根式和不可能恰好落在有理中点，区间收紧后会终止。

复杂度

设街道数为m≤100，坐标与所需精度合并后的最大整数位数为D。读入并计算距离平方 O(mD²)，每轮开方与区间累计 O(mD²)；精度按倍增推进，其总数位运算界仍为 O(mD²)，最终时间换算长除法 O(D²)。存储距离平方 O(mD)，辅助大整数 O(D)。初始化仅保存m个平方距离，不构造显式交叉口图。

易错点

双向车道使总距离乘2，但不需要再把每条有向车道重复计算。停车坐标不直接影响公式，保证连通是关键。50千米/小时仅为空跑速度，而最优欧拉方案无须空跑。输出小时数不截断为两位，分钟必须补齐两位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct cpp_int {
    string s;
    bool neg;
    cpp_int(long long v = 0) : s(to_string(v)), neg(v < 0) {
        if (neg)
            s.erase(s.begin());
    }
    void norm() {
        auto p = s.find_first_not_of('0');
        s = p == string::npos ? "0" : s.substr(p);
        if (s == "0")
            neg = false;
    }
    static int cmpabs(const cpp_int &a, const cpp_int &b) {
        if (a.s.size() != b.s.size())
            return a.s.size() < b.s.size() ? -1 : 1;
        return a.s == b.s ? 0 : a.s < b.s ? -1 : 1;
    }
    friend bool operator<(const cpp_int &a, const cpp_int &b) {
        if (a.neg != b.neg)
            return a.neg;
        int c = cmpabs(a, b);
        return a.neg ? c > 0 : c < 0;
    }
    friend bool operator==(const cpp_int &a, const cpp_int &b) {
        return a.neg == b.neg && a.s == b.s;
    }
    friend bool operator!=(const cpp_int &a, const cpp_int &b) {
        return !(a == b);
    }
    friend bool operator>(const cpp_int &a, const cpp_int &b) {
        return b < a;
    }
    friend bool operator<=(const cpp_int &a, const cpp_int &b) {
        return !(b < a);
    }
    friend bool operator>=(const cpp_int &a, const cpp_int &b) {
        return !(a < b);
    }
    cpp_int operator-() const {
        cpp_int r = *this;
        if (r.s != "0")
            r.neg = !r.neg;
        return r;
    }
    friend cpp_int operator+(const cpp_int &a, const cpp_int &b) {
        cpp_int r;
        r.s.clear();
        int carry = 0;
        if (a.neg == b.neg) {
            int i = (int)a.s.size() - 1, j = (int)b.s.size() - 1;
            while (i >= 0 || j >= 0 || carry) {
                int v = carry + (i >= 0 ? a.s[i--] - '0' : 0) + (j >= 0 ? b.s[j--] - '0' : 0);
                r.s += char('0' + v % 10);
                carry = v / 10;
            }
            r.neg = a.neg;
        } else {
            const cpp_int *x = &a, *y = &b;
            if (cmpabs(a, b) < 0)
                swap(x, y);
            int i = (int)x->s.size() - 1, j = (int)y->s.size() - 1;
            while (i >= 0) {
                int v = x->s[i--] - '0' - carry - (j >= 0 ? y->s[j--] - '0' : 0);
                carry = v < 0;
                if (carry)
                    v += 10;
                r.s += char('0' + v);
            }
            r.neg = x->neg;
        }
        reverse(r.s.begin(), r.s.end());
        r.norm();
        return r;
    }
    friend cpp_int operator-(const cpp_int &a, const cpp_int &b) {
        return a + (-b);
    }
    friend cpp_int operator*(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long carry = 0;
        long long z = b;
        if (z < 0)
            z = -z;
        for (int i = (int)a.s.size() - 1; i >= 0; i--) {
            carry += (a.s[i] - '0') * z;
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        while (carry) {
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        reverse(r.s.begin(), r.s.end());
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    friend cpp_int operator/(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long rem = 0, z = b;
        if (z < 0)
            z = -z;
        for (char c : a.s) {
            rem = rem * 10 + c - '0';
            r.s += char('0' + rem / z);
            rem %= z;
        }
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    cpp_int &operator+=(const cpp_int &b) {
        *this = *this + b;
        return *this;
    }
    cpp_int &operator-=(const cpp_int &b) {
        *this = *this - b;
        return *this;
    }
    cpp_int &operator*=(int b) {
        *this = *this * b;
        return *this;
    }
    friend istream &operator>>(istream &in, cpp_int &a) {
        string v;
        if (in >> v) {
            a.neg = v[0] == '-';
            if (v[0] == '-' || v[0] == '+')
                v.erase(v.begin());
            a.s = v;
            a.norm();
        }
        return in;
    }
    friend ostream &operator<<(ostream &out, const cpp_int &a) {
        if (a.neg)
            out << '-';
        return out << a.s;
    }
};

cpp_int fromString(string s) {
    cpp_int a;
    a.neg = !s.empty() && s[0] == '-';
    if (!s.empty() && (s[0] == '-' || s[0] == '+'))
        s.erase(s.begin());
    a.s = s;
    a.norm();
    return a;
}
cpp_int absBig(cpp_int a) {
    a.neg = false;
    return a;
}
cpp_int pow10(size_t n) {
    cpp_int a;
    a.s = "1" + string(n, '0');
    return a;
}
cpp_int operator*(const cpp_int &a, const cpp_int &b) {
    vector<long long> d(a.s.size() + b.s.size());
    for (int i = (int)a.s.size() - 1; i >= 0; --i)
        for (int j = (int)b.s.size() - 1; j >= 0; --j)
            d[i + j + 1] += (a.s[i] - '0') * (b.s[j] - '0');
    for (int i = (int)d.size() - 1; i > 0; --i) {
        d[i - 1] += d[i] / 10;
        d[i] %= 10;
    }
    cpp_int c;
    c.s.clear();
    for (auto x : d)
        c.s += char('0' + x);
    c.neg = a.neg != b.neg;
    c.norm();
    return c;
}
pair<cpp_int, cpp_int> divmod(cpp_int a, cpp_int b) {
    bool sign = a.neg != b.neg, negrem = a.neg;
    a.neg = b.neg = false;
    cpp_int q, rem;
    q.s.clear();
    cpp_int mul[10];
    for (int i = 0; i < 10; ++i)
        mul[i] = b * i;
    for (char z : a.s) {
        rem = rem * 10 + (z - '0');
        int lo = 0, hi = 9;
        while (lo < hi) {
            int mi = (lo + hi + 1) / 2;
            if (mul[mi] <= rem)
                lo = mi;
            else
                hi = mi - 1;
        }
        q.s += char('0' + lo);
        rem -= mul[lo];
    }
    q.neg = sign;
    q.norm();
    rem.neg = negrem;
    rem.norm();
    return {q, rem};
}
cpp_int floorDiv(cpp_int a, const cpp_int &b) {
    auto z = divmod(a, b);
    if (a.neg && z.second != 0)
        z.first -= 1;
    return z.first;
}
cpp_int rootBig(const cpp_int &a) {
    cpp_int root, rem;
    string s = a.s;
    if (s.size() % 2)
        s = "0" + s;
    for (size_t i = 0; i < s.size(); i += 2) {
        rem = rem * 100 + (s[i] - '0') * 10 + s[i + 1] - '0';
        int x = 9;
        while ((root * 20 + x) * x > rem)
            --x;
        rem -= (root * 20 + x) * x;
        root = root * 10 + x;
    }
    return root;
}
string fixedBig(cpp_int rounded, int digits) {
    bool neg = rounded.neg;
    string s = rounded.s;
    while (s.size() <= (size_t)digits)
        s = "0" + s;
    if (digits)
        s.insert(s.size() - digits, ".");
    return (neg ? "-" : "") + s;
}
cpp_int roundedRational(cpp_int a, cpp_int b) {
    bool neg = a.neg != b.neg;
    a.neg = b.neg = false;
    auto q = divmod(a, b);
    if (q.second * 2 >= b)
        q.first += 1;
    q.first.neg = neg && q.first != 0;
    return q.first;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cpp_int x, y, u, v;
    cin >> x >> y;
    vector<cpp_int> s;
    while (cin >> x >> y >> u >> v) {
        cpp_int dx = x - u, dy = y - v;
        s.push_back(dx * dx + dy * dy);
    }
    size_t precision = 8;
    cpp_int answer;
    for (;;) {
        cpp_int scale = pow10(precision), sqscale = pow10(precision * 2), lo;
        int errors = 0;
        for (auto z : s) {
            cpp_int zz = z * sqscale, h = rootBig(zz);
            lo += h;
            if (h * h != zz)
                ++errors;
        }
        cpp_int den = scale * 500, low = divmod(lo * 3 + scale * 250, den).first,
                high = divmod((lo + errors) * 3 + scale * 250 - (errors ? 1 : 0), den).first;
        if (low == high) {
            answer = low;
            break;
        }
        precision *= 2;
    }
    auto z = divmod(answer, 60);
    cout << z.first << ':' << setw(2) << setfill('0') << z.second << '\n';
}