题目分析

这道题目要求我们找到从起点城市到终点城市的最优火车路线，其中：

1.优先选择到达时间最早的路线

2.如果有多条路线到达时间相同，则选择出发时间最晚的那条

3.换乘时间可以忽略不计（瞬时换乘）

解题思路

算法选择： 使用Bellman-Ford算法的变种 需要两次遍历： 第一次正向遍历，计算最早到达时间 第二次反向遍历，在相同到达时间的情况下选择最晚出发时间

关键步骤： 初始化所有城市的到达时间为极大值 设置起点的到达时间为最早出发时间 使用松弛操作更新到达时间 反向遍历选择最优出发时间

c++实现

#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <iomanip>
using namespace std;

const int MAXN = 1010;

struct Train {
    int time;
    int city;
};

Train change[MAXN][110];
map<string, int> CityNo;
int train[MAXN];
int c, t, start, finish, possible;
int anTime[110];

void search() {
    int i, j, k;
    
    for(i = 1; i <= c; ++i)
        anTime[i] = 1000001;
    anTime[start] = possible;
    
    for(k = 1; k <= c; ++k) {
        for(i = 1; i <= t; ++i) {
            for(j = 1; j < train[i]; ++j) {
                if(change[i][j].time >= anTime[change[i][j].city] 
                && anTime[change[i][j+1].city] > change[i][j+1].time)
                    anTime[change[i][j+1].city] = change[i][j+1].time;
            }
        }
    }
    
    for(i = 1; i <= c; ++i) {
        if(i != finish)
            anTime[i] = -1;
    }
    
    for(k = 1; k <= c; ++k) {
        for(i = 1; i <= t; ++i) {
            for(j = 1; j < train[i]; ++j) {
                if(change[i][j+1].time <= anTime[change[i][j+1].city] 
                && anTime[change[i][j].city] < change[i][j].time)
                    anTime[change[i][j].city] = change[i][j].time;
            }
        }
    }
}

int main() {
    int i, j, nCase = 1;
    while(cin >> c && c) {
        for(i = 1; i <= c; ++i) {
            string szCity;
            cin >> szCity;
            CityNo[szCity] = i;
        }
        
        cin >> t;
        for(i = 1; i <= t; ++i) {
            int nNo;
            cin >> nNo;
            train[i] = nNo;
            for(j = 1; j <= nNo; ++j) {
                int nTime;
                string szCity;
                cin >> nTime >> szCity;
                change[i][j].time = nTime;
                change[i][j].city = CityNo[szCity];
            }
        }
        
        cin >> possible;
        string szStart, szFinish;
        cin >> szStart >> szFinish;
        start = CityNo[szStart];
        finish = CityNo[szFinish];
        
        search();
        
        if(anTime[finish] == 1000001) {
            cout << "Scenario #" << nCase++ << endl
                 << "No connection" << endl << endl;
        } else {
            cout << "Scenario #" << nCase++ << endl
                 << "Departure " << setw(4) << setfill('0') << anTime[start] 
                 << " " << szStart << endl
                 << "Arrival   " << setw(4) << setfill('0') << anTime[finish] 
                 << " " << szFinish << endl << endl;
        }
        CityNo.clear();
    }
    return 0;
}