GESP二级 - 飞行路线：最优路线规划算法 - 常规

GESP二级 - 飞行路线：最优路线规划算法

问题描述

贝茜想要前往一个温暖的地方度过寒冷的冬天。不幸的是，她发现只有一家名叫AB的航空公司愿意卖票给奶牛，而且这些票的价格有些奇怪。AB拥有N架飞机，每架都有一个特定的飞行路线，这个路线包含2个或更多的城市。例如，一架飞机的路线可能是从城市1开始，然后飞到城市5，再飞到城市2，最后飞到城市8。没有城市会在一条路线上出现多次。如果贝茜决定使用这个路线，她可以在一条路线的任意一个城市上飞机，然后在路线上任意一个城市下飞机。她不用一定在第一个城市上飞机，在最后一个城市下飞机。每条路线会有一个价格，不管贝茜沿途经过多少城市，她都要付这么多钱。

贝茜想找到最近的从城市A到城市B的距离。由于她不想被复杂的形成困惑，她想只使用一条单独的路线。请帮她决定她最少应该付多少钱。

输入描述

第1行包含3个数字A、B和N。

下面的2N行，描述可用的路线，每条路线的描述占2行。第一条路线包含路线费用，以及沿途有多少个城市（不超过500个）。第2行包含一个按顺序的城市的列表。

输出描述

输出贝茜用一条飞行路线从城市A飞到城市B的最小费用。如果没有这样的路线，输出“-1”。

例子输入 1

例子输出 1

提示

【数据规模】对于20%的数据满足：N≤10。对于40%的数据满足：N≤100。对于100%的数据满足：N≤10000。

思路

创建一个二维数组routes，用来存储每条路线的费用和城市列表。
创建一个变量minCost，初始值为无穷大，用来记录最小费用。
遍历输入的路线信息，将费用和城市列表存储到routes中。
遍历routes中的每一条路线，判断是否包含城市A和城市B。
如果一条路线同时包含城市A和城市B，就计算这条路线的费用，更新minCost。
如果minCost的值仍然是无穷大，说明没有找到从城市A到城市B的路线，输出-1；否则输出minCost。

代码实现如下

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

int main() {
    int A, B, N;
    cin >> A >> B >> N;

    vector<vector<int>> routes(N, vector<int>());
    for (int i = 0; i < N; i++) {
        int cost, numCities;
        cin >> cost >> numCities;
        routes[i].push_back(cost);
        for (int j = 0; j < numCities; j++) {
            int city;
            cin >> city;
            routes[i].push_back(city);
        }
    }

    int minCost = numeric_limits<int>::max();
    for (int i = 0; i < N; i++) {
        bool containsA = false, containsB = false;
        for (int j = 1; j < routes[i].size(); j++) {
            if (routes[i][j] == A) {
                containsA = true;
            }
            if (routes[i][j] == B) {
                containsB = true;
            }
        }
        if (containsA && containsB) {
            minCost = min(minCost, routes[i][0]);
        }
    }

    if (minCost == numeric_limits<int>::max()) {
        cout << -1 << endl;
    } else {
        cout << minCost << endl;
    }

    return 0;
}

复杂度分析

时间复杂度为O(N*M)，其中N为路线数，M为单条路线的平均城市数。
空间复杂度为O(N*M)，需要额外的空间存储路线信息。