题意分析

本题要求计算欧洲铁路网络中两城市间的最短连接，即不存在其他路线满足以下情况的连接：

1. 晚出发但同时或更早到达：
   存在另一班列车，其出发时间 $d > \text{departure}$，且旅行时间 $tt \leq \text{travelTime}$。
2. 同时出发但更早到达：
   存在另一班列车，其出发时间 $d = \text{departure}$，但旅行时间 $tt < \text{travelTime}$。

输入包含多组测试数据，每组数据给出若干列车路线（含站点、出发时间及相邻站点间的旅行时间），需输出从起点到终点的所有最短连接，按出发时间排序。

解题思路

核心思想

采用动态规划（DP） 结合贪心筛选策略，步骤如下：

1. 预处理列车班次：将每条路线拆解为相邻站点间的具体班次，记录出发站、到达站、出发时间和到达时间。
2. 动态规划计算最早到达时间：对每个可能的出发时间 $t$，用 DP 数组 $\text{earliestArrival}[t]$ 表示在时刻 $t$ 出发时的最早到达时间。
3. 筛选非支配连接：遍历所有可能的出发-到达时间对，排除被其他连接“支配”的情况（即存在更优的出发/到达时间组合）。

实现步骤

1. 数据结构设计

• Time结构体：封装时间的时、分，支持比较、加减运算（如 $\text{Time} + \text{travelTime}$ 计算到达时间）。
• Train结构体：记录单个班次的出发站、到达站、出发时间、到达时间。

2. 输入处理

• 解析每条路线的站点数、出发时间及站点列表，生成相邻站点间的班次。
• 构建邻接表存储所有班次。

3. 动态规划求解最早到达时间

• 对每个可能的出发时间 $\text{departure}$，初始化 $\text{earliestArrival}$ 数组，其中 $\text{earliestArrival}[t]$ 表示在时刻 $t$ 出发的最早到达时间（初始设为极大值）。
• 遍历所有班次，若班次的出发时间 $\text{departure\_time}$ 满足条件（如不早于当前出发时间），则更新 $\text{earliestArrival}[\text{departure\_time}]$ 为更早的到达时间。
• 逆序遍历 $\text{earliestArrival}$ 数组，确保每个时刻的最早到达时间为后续时刻的最优解（即若 $t+1$ 时刻的到达时间更早，则 $t$ 时刻的到达时间更新为该值）。

4. 筛选非支配连接

• 对每个出发时间 $\text{departure}$，计算其对应的最早到达时间 $\text{arrival}$，得到旅行时间 $\text{travelTime} = \text{arrival} - \text{departure}$。
• 若存在其他连接的出发时间 $d$ 和旅行时间 $tt$ 满足以下任一条件，则当前连接被“支配”，不予保留：
  1. $d > \text{departure}$ 且 $tt \leq \text{travelTime}$（晚出发但同时或更早到达）；
  2. $d = \text{departure}$ 且 $tt < \text{travelTime}$（同时出发但更早到达）。
• 否则，保留该连接并更新结果集。

代码实现

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <sstream>  // 添加stringstream头文件

using namespace std;

struct Time {
    int h, m;
    Time(int hh = 0, int mm = 0) : h(hh), m(mm) {}
    bool operator<(const Time& t) const {
        return h < t.h || (h == t.h && m < t.m);
    }
    bool operator==(const Time& t) const {
        return h == t.h && m == t.m;
    }
    Time operator+(const Time& t) const {
        int total = (h * 60 + m) + (t.h * 60 + t.m);
        return Time(total / 60 % 24, total % 60);
    }
    int operator-(const Time& t) const {
        int diff = (h * 60 + m) - (t.h * 60 + t.m);
        return diff < 0 ? diff + 24 * 60 : diff;
    }
};

struct Train {
    string from, to;
    Time departure, arrival;
};

istream& operator>>(istream& is, Time& t) {
    char colon;
    is >> t.h >> colon >> t.m;
    return is;
}

ostream& operator<<(ostream& os, const Time& t) {
    os << (t.h < 10 ? "0" : "") << t.h << ":" 
       << (t.m < 10 ? "0" : "") << t.m;
    return os;
}

// C++98兼容的整数转字符串函数
string intToString(int num) {
    stringstream ss;
    ss << num;
    return ss.str();
}

string formatDuration(int minutes) {
    int h = minutes / 60;
    int m = minutes % 60;
    string res = h > 0 ? intToString(h) : "";
    res += ":";
    if (m < 10) res += "0";
    res += intToString(m);
    return res;
}

int main() {
    int N;
    cin >> N;
    
    for (int caseNum = 0; caseNum < N; ++caseNum) {
        if (caseNum > 0) cout << endl;
        
        int T;
        cin >> T;
        
        vector<Train> trains;
        map<string, vector<Train> > adj;
        
        for (int i = 0; i < T; ++i) {
            int S;
            cin >> S;
            
            Time startTime;
            cin >> startTime;
            
            vector<string> stations(S);
            vector<Time> times(S);
            
            cin >> stations[0];
            times[0] = startTime;
            
            for (int j = 1; j < S; ++j) {
                Time travelTime;
                cin >> travelTime;
                cin >> stations[j];
                times[j] = times[j-1] + travelTime;
                
                Train train;
                train.from = stations[j-1];
                train.to = stations[j];
                train.departure = times[j-1];
                train.arrival = times[j];
                
                trains.push_back(train);
                adj[stations[j-1]].push_back(train);
            }
        }
        
        string origin, destination;
        cin >> origin >> destination;
        
        vector<pair<Time, int> > connections;
        
        for (size_t i = 0; i < trains.size(); ++i) {
            if (trains[i].from != origin) continue;
            
            Time departure = trains[i].departure;
            
            vector<Time> earliestArrival(24*60 + 1, Time(25, 0));
            for (int t = 0; t < 24*60; ++t) {
                earliestArrival[t] = Time(25, 0);
            }
            
            for (size_t j = 0; j < trains.size(); ++j) {
                if (trains[j].from == origin && 
                    (trains[j].departure < departure || 
                     (trains[j].departure == departure && j != i))) {
                    continue;
                }
                if (trains[j].departure.h * 60 + trains[j].departure.m >= 24*60) {
                    continue;
                }
                if (earliestArrival[trains[j].departure.h * 60 + trains[j].departure.m] < trains[j].arrival) {
                    continue;
                }
                earliestArrival[trains[j].departure.h * 60 + trains[j].departure.m] = trains[j].arrival;
            }
            
            for (int t = 24*60 - 1; t >= 0; --t) {
                if (t + 1 < 24*60 && earliestArrival[t+1] < earliestArrival[t]) {
                    earliestArrival[t] = earliestArrival[t+1];
                }
            }
            
            Time bestArrival = earliestArrival[departure.h * 60 + departure.m];
            if (bestArrival.h < 25) {
                int travelTime = (bestArrival.h * 60 + bestArrival.m) - 
                                (departure.h * 60 + departure.m);
                if (travelTime < 0) travelTime += 24 * 60;
                
                bool dominated = false;
                for (size_t j = 0; j < connections.size(); ++j) {
                    int depMin = connections[j].first.h * 60 + connections[j].first.m;
                    int currentDepMin = departure.h * 60 + departure.m;
                    
                    if (depMin > currentDepMin && 
                        (connections[j].second <= travelTime)) {
                        dominated = true;
                        break;
                    }
                    if (depMin == currentDepMin && 
                        connections[j].second < travelTime) {
                        dominated = true;
                        break;
                    }
                }
                
                if (!dominated) {
                    vector<pair<Time, int> > newConnections;
                    for (size_t j = 0; j < connections.size(); ++j) {
                        int depMin = connections[j].first.h * 60 + connections[j].first.m;
                        int currentDepMin = departure.h * 60 + departure.m;
                        
                        if (currentDepMin > depMin && 
                            (travelTime <= connections[j].second)) {
                            continue;
                        }
                        if (currentDepMin == depMin && 
                            travelTime < connections[j].second) {
                            continue;
                        }
                        newConnections.push_back(connections[j]);
                    }
                    newConnections.push_back(make_pair(departure, travelTime));
                    connections = newConnections;
                }
            }
        }
        
        sort(connections.begin(), connections.end());
        
        for (size_t i = 0; i < connections.size(); ++i) {
            cout << connections[i].first << " " 
                 << formatDuration(connections[i].second) << endl;
        }
    }
    
    return 0;
}