题解：P11474 [COCI 2024/2025 #3] 公交车 / Autobus

#include <bits/stdc++.h>
using namespace std;

// 结构体Bus：记录一趟巴士的发车时间(st)和到达时间(ed)，单位为分钟
struct Bus {
    int st, ed;
};

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

    int n; // 巴士总数
    cin >> n;

    // 定义两个容器：zg用于存储Zagreb->Graz线路，gw用于存储Graz->Wroclaw线路
    vector<Bus> zg, gw;
    zg.reserve(n);
    gw.reserve(n);

    // 读取每条巴士信息
    while(n--) {
        string s; // 线路名称，如"Zagreb-Graz"或"Graz-Wroclaw"
        char c1, c2, c3, c4; // 时间格式中的分隔符，例如':'和'--'
        int h1, m1, h2, m2;  // 小时、分钟
        cin >> s >> h1 >> c1 >> m1 >> c2 >> c3 >> h2 >> c4 >> m2;

        // 将"时:分"转换为从0:00开始计算的总分钟数
        int st = h1 * 60 + m1;
        int ed = h2 * 60 + m2;

        // 若到达时间ed小于发车时间st，说明跨天，需修正为+24小时
        ed += (st - ed + 1440) / 1440 * 1440;

        // 根据线路分发到对应容器
        if(s[0] == 'Z') zg.push_back({st, ed});
        else gw.push_back({st, ed});
    }

    // 初始化最短时间为极大值
    int ans = INT_MAX;

    // 将所有Zagreb-Graz线路与Graz-Wroclaw线路进行匹配
    for(const auto &b1 : zg) {
        for(const auto &b2 : gw) {
            // 为保证换乘满足"第一段到达时间<第二段发车时间"，再对第二段到达时间做跨天修正
            int ed2 = b2.ed;
            ed2 += (b1.ed - b2.st + 1440) / 1440 * 1440;

            // ans取最小值，将两段总耗时(b2到达时间 - b1出发时间 + 1)最小化
            ans = min(ans, ed2 - b1.st + 1);
        }
    }

    // 输出结果
    if(ans == INT_MAX) {
        // 若无可行方案，则输出"NEMOGUCE"
        cout << "NEMOGUCE";
    } else {
        // 将分钟数ans转为"小时:分钟"形式
        cout << ans / 60 << ':';
        if(ans % 60 < 10) cout << 0; // 若分钟只有一位，在前面补0
        cout << ans % 60;
    }
}