下面以去往城市0的航班为例（从城市0返回的航班同理）进行分析：

• 首先，将去的航班按照日期排好序。
• 然后我们可以发现：对于同一个城市来说，如果有航班A和航班B两次航班，A的时间早、票价低，B的时间晚、票价高，则B无需考虑。根据这样的规律，可以过滤掉一波无用的数据。接下来只考虑过滤后的数据。
• 过滤之后可以发现：对于同一个城市来说，目前剩下的航班的价格是按照时间依次递减的。或者说，此时如果有C和D两个航班从同一个城市起飞，C比D早，那么D一定比C便宜。如果在时间允许的情况下（即航班D能够满足k天的要求），那么D之前的所有航班都可以选择；而此时D又是从该城市起飞的航班中最便宜的，因此此时选择D是最优的。如果有航班E比D要晚，并且E满足k天的需求，那么选择E一定比选择D更优。
• 根据这样的规律，我们可以计算出to_cost数组。to_cost数组中的第i项存放的是：如果只从前i个航班中进行选择，所有人飞往城市0花费的最小总和。这个数组是递减的 – 如果选择了第i个航班，它是从城市j起飞的，那么一定比选择比i更早的从城市j起飞的航班要优。这个数组的计算方法也很简单：假设第i个航班从城市j起飞，上一个从城市j起飞的航班的花费设为last_j_cost， 则 to_cost[i] = to_cost[i - 1] - (last_j_cost - flight[i].cost)
• 回来的航班也如此计算出 back_cost。
• 接下来只要同时对两个数组进行遍历就可以了。两个数组都从头开始，如果满足k天的要求，则计算出新的最小值，然后to_cost向后遍历；如果不满足k天的要求，则back_cost向后遍历。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;


struct Flight {
    int day;
    int city;
    int cost;

    bool operator < (const Flight& rhs) const {
        return day < rhs.day;
    }
};

struct TotalCost {
    int day;
    long long total_cost;

    TotalCost(int _day, long long _total_cost)
        : day(_day), total_cost(_total_cost) {

    }
};

long long calc_cost(vector<Flight>& choice) {
    long long cost = 0;
    for (int i = 0; i < choice.size(); i++) {
        cost += choice[i].cost;
    }
    return cost;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<Flight> flights_to;
    vector<Flight> flights_back;

    for (int i = 0; i < m; i++) {
        Flight flight;
        int from, to;
        cin >> flight.day >> from >> to >> flight.cost;

        if (to == 0) {
            flight.city = from - 1;
            flights_to.push_back(flight);
        }
        else {
            flight.city = to - 1;
            flights_back.push_back(flight);
        }
    }

    sort(flights_to.begin(), flights_to.end());
    sort(flights_back.begin(), flights_back.end());

    set<int> city_id;
    vector<Flight> choices_to(n);
    vector<Flight> choices_back(n);
    int start_day = 999999;
    int end_day = 0;
    int start_id, end_id;

    // Choose the earlest start day
    for (int i = 0; i < flights_to.size(); i++) {
        if (city_id.find(flights_to[i].city) != city_id.end()) {
            if (choices_to[flights_to[i].city].cost > flights_to[i].cost) {
                choices_to[flights_to[i].city] = flights_to[i];
            }
            continue;
        }
        city_id.insert(flights_to[i].city);
        choices_to[flights_to[i].city] = flights_to[i];
        if (city_id.size() == n) {
            start_day = flights_to[i].day;
            start_id = i;
            break;
        }
    }

    if (city_id.size() != n) {
        cout << -1 << endl;
        return 0;
    }

    city_id.clear();

    // Choose the latest end day
    for (int i = flights_back.size() - 1; i >= 0; i--) {
        if (city_id.find(flights_back[i].city) != city_id.end()) {
            if (choices_back[flights_back[i].city].cost > flights_back[i].cost) {
                choices_back[flights_back[i].city] = flights_back[i];
            }
            continue;
        }
        city_id.insert(flights_back[i].city);
        choices_back[flights_back[i].city] = flights_back[i];
        if (city_id.size() == n) {
            end_day = flights_back[i].day;
            end_id = i;
            break;
        }
    }

    if (city_id.size() != n) {
        cout << -1 << endl;
        return 0;
    }

    if (end_day - start_day - 1 < k) {
        cout << -1 << endl;
        return 0;
    }

    vector<TotalCost> to_cost, back_cost;
    to_cost.push_back(TotalCost(flights_to[start_id].day, calc_cost(choices_to)));
    back_cost.push_back(TotalCost(flights_back[end_id].day, calc_cost(choices_back)));

    vector<Flight> mins = choices_to;
    for (int i = start_id; i < flights_to.size(); i++) {
        int city_id = flights_to[i].city;
        long long m = mins[city_id].cost - flights_to[i].cost;
        if (m > 0) {
            to_cost.push_back(TotalCost(flights_to[i].day, to_cost.back().total_cost - m));
            mins[city_id] = flights_to[i];
        }
    }

    mins = choices_back;
    for (int i = end_id; i >= 0; i--) {
        int city_id = flights_back[i].city;
        long long m = mins[city_id].cost - flights_back[i].cost;
        if (m > 0) {
            back_cost.push_back(TotalCost(flights_back[i].day, back_cost.back().total_cost - m));
            mins[city_id] = flights_back[i];
        }
    }

    reverse(back_cost.begin(), back_cost.end());
    int i = 0, j = 0;
    long long min_cost = LLONG_MAX;
    while (true) {
        if (back_cost[j].day - to_cost[i].day - 1 >= k) {
            if (to_cost[i].total_cost + back_cost[j].total_cost < min_cost) {
                min_cost = to_cost[i].total_cost + back_cost[j].total_cost;
            }
            i++;
        }
        else {
            j++;
        }
        if (i >= to_cost.size() || j >= back_cost.size())
            break;
    }

    while (j < back_cost.size()) {
        if (to_cost[i - 1].total_cost + back_cost[j].total_cost < min_cost) {
            min_cost = to_cost[i - 1].total_cost + back_cost[j].total_cost;
        }
        j++;
    }

    cout << min_cost << endl;

    return 0;
}