问题描述

给定多个火车路线的时刻表，每条路线包含多个车站和相邻车站之间的旅行时间。火车每天在同一时间发车。需要找出从起点站到终点站的所有 最短连接 ，即满足以下条件的连接：不存在另一个连接可以让你 更晚出发 并在 相同时间或更早到达 ，或者 同一时间出发 但 更早到达 。

输入格式

• 第一行：测试用例数量 $N$
• 每个测试用例：
  • 第一行：火车路线数量 $T\le 20$
  • 接下来 $T$ 条路线的描述：
    • 每个路线：车站数量 $S\le 20$ ，出发时间 $hh:mm$ ，车站列表和相邻车站间的旅行时间
  • 最后一行：起点站和终点站名称

输出格式

对于每个测试用例，按出发时间升序输出所有最短连接的出发时间和旅行时间，相同出发时间只输出一次。连续测试用例间空一行。

解题思路分析

1. 问题核心理解

题目要求的是 帕累托最优解 （$\text{Pareto optimal}$），即在 (出发时间, 到达时间) 二维空间中的前沿。一个连接 $(d_1,a_1)$ 被另一个连接 $(d_2,a_2)$ 支配 ，如果 $d_2\ge d_1$ 且 $a_2\le a_1$ ，且至少有一个严格不等式。

关键观察：对于每个固定的出发时间，我们只关心最早到达时间。因此问题转化为：对于每个可能的出发时间（$0$ 到 $1439$ 分钟），计算最早到达时间，然后从这些 (出发时间, 最早到达时间) 对中过滤出帕累托前沿。

2. 算法设计

2.1 状态定义

定义 $dp[station][time]$ 表示从起点出发，在车站 $station$ 的时间 $time$ （$0$ 到 $1439$ 分钟）时，所需的最短旅行时间（分钟）。

这里 $time$ 是 $24$ 小时制下的时间，$dp$ 值是从起点到该状态的实际耗时。

2.2 状态转移

对于每条火车边：从车站 $u$ 到车站 $v$ ，出发时间 $depart$ ，旅行时间 $travel$ ，到达时间 $arrive=(depart+travel)\mathrm{mod}1440$ 。

如果可以在 $depart$ 时间从 $u$ 出发（即 $dp[u][depart]$ 不是无穷大），那么：

• 到达 $v$ 的时间为：$newTime=dp[u][depart]+travel$
• 到达 $v$ 的车站时间为：$arrive$

状态更新：
$$dp[v][arrive]=\min (dp[v][arrive],newTime)$$

关键优化：如果 $dp[v][arrive]$ 被更新为更小的值，那么对于 $arrive$ 之后的所有时间点 $t$ ，都可以通过在车站等待达到，因此也需要更新：
$$dp[v][t]=\min (dp[v][t],newTime+(t-arrive)\mathrm{mod}1440)$$

这里 $(t-arrive)\mathrm{mod}1440$ 是等待时间。

2.3 算法流程

1. 初始化：起点站所有时间的 $dp$ 值为 $0$ ，其他车站为无穷大。
2. 动态规划/松弛：不断应用状态转移，直到没有更新为止。
3. 结果提取：对于终点站的每个时间 $t$ ，如果 $dp[end][t]<\infty$ ，则：
   • 旅行时间 = $dp[end][t]$
   • 出发时间 = $(t-dp[end][t])\mathrm{mod}1440$
4. 帕累托过滤：按出发时间排序，去除相同出发时间的重复项（保留旅行时间最短的）。

3. 算法正确性证明

3.1 最优子结构

$dp[station][time]$ 存储的是从起点到该状态的最短时间，这具有最优子结构性质：到达一个状态的最优解可以通过到达前驱状态的最优解加上转移代价得到。

3.2 松弛的完备性

由于时间循环的特性（模 $1440$ ），可能需要多次松弛才能收敛。算法中的 $while$ 循环确保所有可能的状态转移都被考虑，直到没有改进为止。

3.3 帕累托最优性

对于每个出发时间 $d$ ，我们找到最早到达时间 $a$ 。如果存在另一个连接 $(d^{\prime },a^{\prime })$ 支配 $(d,a)$ ，那么：

• 如果 $d^{\prime }>d$ 且 $a^{\prime }\le a$ ，那么对于出发时间 $d^{\prime }$ ，到达时间 $a^{\prime }$ 更优
• 如果 $d^{\prime }=d$ 且 $a^{\prime }<a$ ，那么 $a$ 不是最早到达时间

因此，通过保留每个出发时间的最早到达时间，并过滤非支配解，我们得到帕累托前沿。

4. 时间复杂度分析

设车站数为 $M$ （最多 $20\times 20=400$ ），边数为 $E$ （最多 $20\times 19=380$ ），时间维度为 $1440$ 。

• 状态数：$O(M\times 1440)$
• 每次松弛：$O(E)$
• 最坏情况松弛次数：$O(1440)$ （每个时间点可能被更新一次）
• 总时间复杂度：$O(1440\times E\times 1440)\approx O(10^8)$ ，但在实际数据中收敛很快。

5. 关键实现细节

5.1 时间处理

所有时间统一转换为分钟表示，便于计算。需要注意模 $1440$ 运算处理跨天情况。

5.2 状态更新优化

当更新 $dp[v][arrive]$ 时，同时更新 $arrive$ 之后的所有时间点，因为可以在车站等待。这是算法的关键优化，避免了为每个时间点单独计算。

5.3 无穷大值选择

使用 0x3f3f3f3f 作为无穷大，这个值足够大且不会溢出。

代码实现

// Trains
// UVa ID: 10362
// Verdict: Accepted
// Submission Date: 2026-01-30
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

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

const int MINUTES_PER_DAY = 1440;  // 每天的分钟数
const int INF = 0x3f3f3f3f;        // 无穷大值

// 将时间字符串 "hh:mm" 转换为分钟数
int toMinutes(const string& s) {
    int p = s.find(':');
    int hour = stoi(s.substr(0, p));
    int minute = stoi(s.substr(p + 1));
    return hour * 60 + minute;
}

// 将分钟数格式化为 "hh:mm"
string fmtTime(int minutes) {
    char buf[16];
    sprintf(buf, "%02d:%02d", minutes / 60, minutes % 60);
    return string(buf);
}

// 将分钟数格式化为旅行时间 "h:mm"
string fmtTravel(int minutes) {
    char buf[16];
    sprintf(buf, "%d:%02d", minutes / 60, minutes % 60);
    return string(buf);
}

int main() {
    int N; cin >> N;  // 测试用例数量
    bool firstCase = true;  // 标记是否为第一个测试用例
    
    while (N--) {
        // 输出用例间的空行（第一个除外）
        if (!firstCase) cout << '\n';
        firstCase = false;
        
        int T; cin >> T;  // 火车路线数量
        
        // 车站映射：名称 -> ID
        map<string, int> stationId;
        vector<string> stationNames;
        
        // 存储所有火车边
        struct TrainEdge { 
            int fromStation;   // 起点站ID
            int toStation;     // 终点站ID
            int departTime;    // 出发时间（0-1439）
            int travelTime;    // 旅行时间（分钟）
        };
        vector<TrainEdge> edges;
        
        // 读取所有路线
        for (int r = 0; r < T; r++) {
            int S; string s; 
            cin >> S >> s;  // 车站数量和路线出发时间
            int routeStartTime = toMinutes(s);  // 转换为分钟
            
            // 存储路线信息：(车站ID, 到达时间偏移)
            vector<pair<int, int>> routeInfo;
            
            string stationName; cin >> stationName;
            // 获取或创建车站ID
            if (!stationId.count(stationName)) {
                stationId[stationName] = stationNames.size();
                stationNames.push_back(stationName);
            }
            int station = stationId[stationName];
            routeInfo.push_back({station, 0});  // 第一个车站时间偏移为0
            
            int totalTime = 0;  // 累计旅行时间
            for (int i = 1; i < S; i++) {
                string nextStation;
                cin >> s >> nextStation;  // 旅行时间和下一站名
                
                int travelTime = toMinutes(s);  // 转换为分钟
                totalTime += travelTime;
                
                if (!stationId.count(nextStation)) {
                    stationId[nextStation] = stationNames.size();
                    stationNames.push_back(nextStation);
                }
                int nextId = stationId[nextStation];
                routeInfo.push_back({nextId, totalTime});
            }
            
            // 为相邻车站创建火车边
            for (int i = 0; i < S - 1; i++) {
                TrainEdge edge;
                edge.fromStation = routeInfo[i].first;
                edge.toStation = routeInfo[i + 1].first;
                // 出发时间 = 路线出发时间 + 当前车站时间偏移（模1440）
                edge.departTime = (routeStartTime + routeInfo[i].second) % MINUTES_PER_DAY;
                // 旅行时间 = 下一站时间偏移 - 当前站时间偏移
                edge.travelTime = routeInfo[i + 1].second - routeInfo[i].second;
                edges.push_back(edge);
            }
        }
        
        // 读取起点和终点
        string startName, endName; 
        cin >> startName >> endName;
        int startId = stationId[startName];
        int endId = stationId[endName];
        
        // 动态规划数组：travel[station][time] = 从起点到该车站在该时间所需的最短时间
        vector<vector<int>> travel(stationNames.size(), 
                                  vector<int>(MINUTES_PER_DAY, INF));
        
        // 初始化：起点站在所有时间都已经到达（时间为0）
        for (int t = 0; t < MINUTES_PER_DAY; t++) 
            travel[startId][t] = 0;
        
        // 动态规划：不断松弛直到没有更新
        bool updated = true;
        while (updated) {
            updated = false;
            
            for (const auto& edge : edges) {
                int from = edge.fromStation;
                int to = edge.toStation;
                int depart = edge.departTime;
                int travelTime = edge.travelTime;
                int arrive = (depart + travelTime) % MINUTES_PER_DAY;
                
                // 如果可以在depart时间从from站出发
                if (travel[from][depart] < INF) {
                    int newArrivalTime = travel[from][depart] + travelTime;
                    
                    // 更新到达时间及之后的所有时间
                    int currentTime = arrive;
                    int currentArrival = newArrivalTime;
                    
                    // 只要当前时间点的值大于新的到达时间，就更新
                    while (travel[to][currentTime] > currentArrival) {
                        updated = true;
                        travel[to][currentTime] = currentArrival;
                        
                        // 移动到下一个时间点（可以在车站等待）
                        currentTime = (currentTime + 1) % MINUTES_PER_DAY;
                        currentArrival++;
                    }
                }
            }
        }
        
        // 收集所有可能的连接
        vector<pair<int, int>> connections;  // (出发时间, 旅行时间)
        
        for (int arrivalTime = 0; arrivalTime < MINUTES_PER_DAY; arrivalTime++) {
            if (travel[endId][arrivalTime] < INF) {
                int travelTime = travel[endId][arrivalTime];
                // 出发时间 = 到达时间 - 旅行时间（模1440）
                int departTime = (arrivalTime - travelTime) % MINUTES_PER_DAY;
                if (departTime < 0) departTime += MINUTES_PER_DAY;
                
                connections.push_back({departTime, travelTime});
            }
        }
        
        // 按出发时间排序
        sort(connections.begin(), connections.end());
        
        // 输出结果：过滤帕累托前沿
        vector<pair<int, int>> result;
        for (size_t i = 0; i < connections.size(); i++) {
            // 相同出发时间只保留第一个（旅行时间最短的）
            if (i == 0 || connections[i].first != connections[i - 1].first) {
                result.push_back(connections[i]);
            }
        }
        
        // 输出最终结果
        for (auto r : result) {
            cout << fmtTime(r.first) << ' ' << fmtTravel(r.second) << '\n';
        }
    }
    
    return 0;
}

总结

本题的核心是理解 帕累托最优 在时间维度上的应用，以及如何通过动态规划在状态空间 $(station,time)$ 上找到最优解。算法的关键在于：

1. 状态设计：$dp[station][time]$ 表示从起点到该状态的最短时间
2. 状态转移：考虑火车班次和车站等待
3. 优化：批量更新到达时间之后的所有时间点
4. 结果提取：从终点站的状态反推出发时间

这种基于时间的动态规划方法在处理时刻表类问题时非常有效，可以推广到类似的调度和路径规划问题中。