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。

解题思路

首先，根据输入的城市A和城市B，遍历所有路线，找到包含城市A和城市B的路线。记录下这些路线的费用。

然后，遍历所有路线，找到包含城市A的路线。对于每条包含城市A的路线，我们需要找到另一条包含城市B的路线，使得这两条路线的费用之和最小。具体操作如下：

对于每条包含城市A的路线，计算到达城市B的最小费用。即，找到另一条包含城市B的路线，使得这两条路线的费用之和最小。
在第1步中找到的包含城市B的路线中，找到到达城市A的最小费用。即，找到另一条包含城市A的路线，使得这两条路线的费用之和最小。
计算这两条路线的费用之和，并记录下最小值。

最后，输出记录下的最小费用。

代码如下

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

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

    unordered_map<int, vector<int>> routes;
    for (int i = 0; i < N; i++) {
        int cost, numCities;
        cin >> cost >> numCities;

        vector<int> cities(numCities);
        for (int j = 0; j < numCities; j++) {
            cin >> cities[j];
        }
        routes[i] = cities;
    }

    vector<int> costsFromA;
    vector<int> costsToB;

    for (int i = 0; i < N; i++) {
        vector<int> cities = routes[i];
        if (find(cities.begin(), cities.end(), A) != cities.end()) {
            costsFromA.push_back(i);
        }
        if (find(cities.begin(), cities.end(), B) != cities.end()) {
            costsToB.push_back(i);
        }
    }

    int minCost = -1;
    for (int i : costsFromA) {
        vector<int> citiesA = routes[i];
        int costA = 0;
        for (int j = 0; j < citiesA.size() - 1; j++) {
            if (citiesA[j] == A) {
                break;
            }
            costA += citiesA[j];
        }

        int minCostB = INT_MAX;
        for (int k : costsToB) {
            vector<int> citiesB = routes[k];
            int costB = 0;
            for (int j = 0; j < citiesB.size() - 1; j++) {
                if (citiesB[j] == B) {
                    break;
                }
                costB += citiesB[j];
            }
            minCostB = min(minCostB, costB);
        }
        if (minCostB != INT_MAX) {
            minCost = (minCost == -1) ? costA + minCostB : min(minCost, costA + minCostB);
        }
    }

    cout << minCost << endl;

    return 0;
}